Is this tail recursion?

Question

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

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 the question does not use a tail recursion. A tail recursion is easily recognizable: the recursive step is the last thing that happens in the method.

In your code, after both recursive calls end, there's one more operation to do - an addition. So the method is recursive, but not tail-recursive.

For comparison purposes, here's a tail-recursive implementation of the fib() method - notice how we need to pass extra parameters to save the state of the recursion, and more importantly, notice that there are no operations left to do after 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 like this:

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

The previous implementation will work fine up to n=92, for bigger numbers you'll have to use BigInteger instead of long, and better switch to an iterative algorithm.

Answer 2

@Óscar López has answered the Question.

The reason that people are interested in knowing whether a call is tail call is that there is an optimization that allows a tail call to be replaced with a branch, thereby avoiding the need to create a new stack frame. This allows unbounded tail recursion on a bounded stack.

However, since you tagged the Question with java, you should know that current Java implementations DO NOT implement tail call optimization. A deeply recursive method call in Java is liable to result in a StackOverflowError.