We all have used Recursion few to many times in our programming journey. Recursion is an approach/strategy of solving a problem such that the solution depends on the smaller/reduced version of the same problem.
Let us consider calculating the Factorial of a number.
Factorial
package com.kapil.recursion;
public class FactorialRecursion {
public static void main(String[] args) {
System.out.println(calculateFactorial(5));
System.out.println(calculateFactorialTailRec(5));
}
private static long calculateFactorial(long inputNumber) {
if(inputNumber == 0 || inputNumber == 1) {
return 1;
}
else {
return inputNumber * calculateFactorial(inputNumber - 1);
}
}
private static long calculateFactorialTailRec(long inputNumber) {
long accumulator = 1;
return calculateFactorialTailRec(inputNumber, accumulator);
}
private static long calculateFactorialTailRec(long inputNumber, long accumulator) {
if(inputNumber == 0 || inputNumber == 1) {
return accumulator;
}
else {
return calculateFactorialTailRec(inputNumber - 1 , inputNumber * accumulator);
}
}
}
Output :
The above piece of code uses 2 approaches to calculate the Factorial of a number :
- Normal Recursion (calculateFactorial())
- Tail Recursion (calculateFactorialTailRec())
For Option No. 1 we can see at Line No. 10 we are checking for our base condition or the breaking condition and if it is not satisfied we are recursively calling the same function in a recursive manner as highlighted in Line No. 14.
We have been using this form of Recursion since quite some time but the problem arises for large to very large numbers. As we know this form of Recursion uses Stack to capture/temporarily store the state of the very call before it can further make a nested/recursive call. We keep on storing the intermediate values in stack till we reach the base condition and then start unwinding/popping out the intermediate results that were stored onto the stack. Even though these days we have sufficient memory available at our disposal but still this approach can result in the Stack frame growing and us landing up with performance and memory issues.
Let us now see how Option No. 2 i.e. Tail Recursion helps to address this issue and handles the very same problem via a different approach.
In Tail Recursion, we generally go with the concept of an Accumulator. An Accumulator is like a variable that is supposed to hold the updated result of the calculations/operations that have been performed so far.
If we see the implementation for calculateFactorialTailRec(), we can see we start with an accumulator as highlighted in Line No. 19. We check for the base condition like earlier but rather than returning the hardcoded value 1, we return the accumulator.
If we see Line No. 28, here we are passing both the inputNumber - 1 as the 1st argument (like in Plain recursion) as well as the 2nd argument that contains the updated value of the calculation so far. Thus we can see in this particular approach, we are not storing any intermediate result as part of our recursive invocation and whatever intermediate value needs to be used is passed as the 2nd argument.
With this approach since we do not need to store any intermediate result values in Stack frame (only the invocations are tracked in the stack), this approach is both performant and memory efficient at the same time.
The sample code is available @ https://github.com/kapilmonadi/TailRecursion
So that’s it for this post. Go ahead and run this piece of code in your favorite java editor.
See you until next time. Happy Learning !