Search This Blog

Tuesday, November 13, 2018

Example of Tail Recursion

Python:
def factorial(i, current_factorial=1): 
if i == 1:   
 return current_factorial 
else:   
 return factorial(i - 1, current_factorial * i)
Java:
factorial1(n, accumulator) {   
if (n == 0) return accumulator;   
return factorial1(n - 1, n * accumulator);  }
factorial(n) {  return factorial1(n, 1);  }
In tail recursion, the recursive calls do not need a new stack frame for each and every recursive call that is made. This is because the calculation is made within the function parameters/arguments – and the final function call actually contains the final result, and the final result does not rely on the return value of each and every recursive call. But it is up to the compiler/interpreter of the particular language to determine whether or not the recursive calls in a tail recursive function actually use an extra stack frame for each recursive call to the function.


Both tail call optimization and tail call elimination mean exactly the same thing and refer to the same exact process in which the same stack frame is reused by the compiler, and unnecessary memory on the stack is not allocated. Tail Recursion optimization is not supported by either Java or Python. ( Some JVM implementations do support tail call optimization as an add-on )