A recursive function is said to be tail-recursive if there is nothing to do after the function returns except returning its value. In this case, instead of allocating a stack frame for each call, the compiler can rework the code to simply reuse the current stack frame, meaning a tail-recursive function will only use a single stack frame as opposed to hundreds or even thousands of stack frame as in the case of regular recursive calls.

Also, in a tail-recursive case, with each evaluation of the recursive call, the solution (e.g., a running total) is updated through parameter. A smart compiler can make Tail Recursion as efficient as iteration normally is.

We'll see an tail-recursion implementation of Fibonacci at the end of this post. Using Fibonacci as an example, a Fibonacci sequence: [f(0)...f(n)]=[0, 1, 1, 2, 3, 5, 8, 13, ...]

public double fib(int n) {

if(n == 0)

return 0d;

else if(n == 1)

return 1d;

else

return fib(n - 1) + fib(n - 2);

}

fib(100)

= fib(99) + fib(98)

= fib(98) + fib(97) + fib(97) + fib(96)

= fib(97) + fib(96) + fib(96) + fib(95) + fib(96) + fib(95) + fib(95) + fib(94)

= ...

double f(int n){

double prev_prev=0d, prev=1d, result=0d;

for (int i = 1; i <n; i++) {

result=prev_prev+prev;

prev_prev=prev;

prev=result;

}

return result;

}

Can't we stay with the recursive way of implementation? Sure. I view tail recursion as a way of introducing a running total which is updated through parameter of the recursive calls. In the Fabonacci example below, 'running tatal' is updated and maintained through 'val' parameter, and the previous value to be calculated toward Fabonocci is passed through the 'prev' parameter:

double fib(int term, double val = 1d, double prev = 0d)

double fib(int term, double val = 1d, double prev = 0d){

if(term == 0) return prev;

if(term == 1) return val;

return fib(term - 1, val+prev, val);

}