Is it tail recursion?

Question

I tried to find examples of tail recursion, and I really don't see the difference between regular and tail. If it's not tail recursion, can someone tell me why it's not there?

public static long fib(long index) { // assume index >= 0 if (index == 0) // Base case return 0; else if (index == 1) // Base case return 1; else // Reduction and recursive calls return fib(index - 1) + fib(index - 2); } // end of method fib(long index) 

Answer 1

No, the method in question does not use tail recursion. Tail recursion is easily recognizable: a recursive step is the last thing that happens in a method.

After completing both recursive calls, there is one more operation in your code - adding. Thus, the method is recursive, but not recursive.

For comparison purposes, here is the recursive implementation of the fib() method - pay attention to how we need to pass additional parameters to save the state of the recursion and, more importantly, to notice that after the operation there were no actions, the recursive call returns.

 public static long fib(int n, long a, long b) { return n == 0 ? b : fib(n-1, a+b, a); } 

Use it as follows:

 fib(10, 1, 0) // calculates the fibonacci of n=10 => 55 

The previous implementation will work up to n = 92, for large numbers you will have to use BigInteger instead of long and it is better to switch to an iterative algorithm.

Answer 2

@ Óscar López answered the question.

The reason people are interested in understanding whether a call is tail is because there is an optimization that allows replacing a tail call with a branch, thereby avoiding the need to create a new stack frame. This allows unlimited tail recursion in a limited stack.

However, since you flagged the issue with java , you should be aware that current Java implementations DO NOT implement tail call optimization. A call with a deep recursive method in Java can StackOverflowError .