Factorial in Java and What is Tail Recursion

If You have ever written factorial program using recursion You have faced StackOverFlowError as Java does not fully support recursion for large iteration.

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).

Recursions are really cool and highly expressive. Recursions don’t scale very well for large input sizes. And in practical way, I want to use recursions when the problem size is complex and big. So, it kind of defeats the purpose. You can’t use it when you need it the most.

To write effective recursion program We need to use Tail Recursion concept. Lets write factorial logic using Tail Recursion concept –

1
2
3
4
5
6
7
8
private static int fact(int n, int k) {
if (n == 0) return k;
else return fact(n - 1, n * k);
}

public static int factorial(int n) {
return fact(n, 1);
}

 

Notice that for the first call, the parameter k is initialized to 1. This relates to the basis case: when n is 0 then the function should return 1.

 

Motivation behind the tail recursion
There’s an important difference in behavior between the recursive and the tail recursive implementations. These difference is visible through the the call stack. In the recursive case, the result is built as you come back from recursive calls. Here is the different states of the call stack in recursive version when we call factorial(5):

factorial using normal recursion

 

Now, you can see the call stack for the tail recursive implementation for the same call:

Tail Recursion

 

You can notice that when we’re coming back from the recursive calls here, the same value is returned. Thus, we can easily imagine to optimize the tail recursive implementation. In fact, there two possible optimizations at this level. The first one is call trampolining. It consists in generating some small modification where recursive call is marked bounce and return is marked landing.

Read More

You may also like

Leave a Reply

Your email address will not be published. Required fields are marked *