To compute the values of this function for a certain set of inputs, it’s necessary to evaluate it for another set of input data. In other words, this is a function which calls itself. The most known examples of recursion are factorial (as the majority of programming books say) and Fibonacci numbers. Let’s forget about factorial and see how the implementation of Fibonacci numbers looks in
Java:
public static int fib(int n) {
if (n > 1) return fib(n - 1) + fib(n - 2);
else return n;
}
As we can notice from the example, before returning the value from the function, two calls of the same function occur but with other values.
Tail recursion
Now, we get back to the tail recursion. It will be tail if the call of recursion function is the last operation before the return of function. Let's try to rewrite the previous example by using the tail recursion:
public static int fibWithTailRec(int n) {
if (n > 1) return fibIter(1, 1, n - 2);
else return n;
}
private static int fibIter(int prev, int current, int n) {
if (n == 0) return current;
else return fibIter(current, prev + current, n - 1);
}
API of the class hasn't changed: we still have a method that returns the value of the n-th Fibonacci number. We also have a new private method fibIter, which contains tail recursion. Very often, to implement tail recursion, a helper method is used. This method takes a recursive state before the next iteration. Due to this, tail recursive function can be represented as a loop.
public static int fibWithLoop(int n) {
if (n <= 1) return n;
int i = 2;
int prev = 1;
int current = 1;
while (i < n) {
int next = prev + current;
prev = current;
current = next;
i += 1;
}
return current;
}
This code looks awful and there are many places where you can make a mistake. That's why, the recursive solutions are often more efficient due to their brevity and readability.
Let's check our functions under a pressure and compute the 10000th element of the sequence. Unfortunately, both methods - fib and fibWithTailRec - will throw java.lang.StackOverflowError. This means that recursions in Java should be used carefully.
