Tail Recursion

1. Motivation

Recursion is a frequently adopted pattern for solving some sort of algorithm problems that need to divide and conquer a big issue and solve the smaller but the same issue first. For example, calculating Fibonacci accumulating sum and calculating factorials.

In these kinds of issues, recursion is more straightforward than their loop counterpart. Furthermore, recursion may need less code and looks more concise.

For example, let's calculate sum of a set of numbers starting with 0 and stopping at N where N might be a large number. The loop way is quite simple for this issue.

1.1 For Loop

private static int sumWithLoop(int n) {
    int sum = 0;
    for(int i = 1; i <= n; ++i) {
        sum += i;
    }
    return sum;
}

1.2 Using Recursion

private static int sumWithTraditionalRecursion(int n) {
    if(0 == n) {
        return n;
    } else {
        return n + sumWithTraditionalRecursion(n-1);
    }
}

1.1 StackOverflow Problem

If the recursive calculations become too many, there is a potential of Stackoverflow issue. This is because when every method is invoked with the state(temp variables, intermediate values to be stored), there will be a stack created for it, the intermediate value will be used to calculate the final result when the recursion call returns. So when a recursive call occurs, there will be an intermediate value stored for each recursive call until the stop condition reaches. Unfortunately, a modern interpreter or virtual machine will often have a stack limit which limits the number of stacks created. If this limit is exceeded, there will be StackOverflowError or similar happening.

Let's take the above "sumWithTraditionalRecursion" example and set n to a large number such as 200000. Then run the program again and a StackOverflowError will happen.

Exception in thread "main" java.lang.StackOverflowError
    at interview.RecursionTest.sumWithTraditionalRecursion(RecursionTest.java:17)
    at interview.RecursionTest.sumWithTraditionalRecursion(RecursionTest.java:17)
    at interview.RecursionTest.sumWithTraditionalRecursion(RecursionTest.java:17)
    at interview.RecursionTest.sumWithTraditionalRecursion(RecursionTest.java:17)
    at interview.RecursionTest.sumWithTraditionalRecursion(RecursionTest.java:17)

2. Tail Recursion

Tail recursion is also a kind of recursion but it will make the return value of the recursion call as the last statement of the method. This will make the calculation occurs before the recursion call and hence there is no need to keep the stack to store the intermediate value when it moves to the next recursive call. 

private static int sumWithTailRecursion(int n, int sum) {
    if(0 == n) {
        return sum;
    } else {
        return sumWithTailRecursion(n-1, sum + n);
    }
}

One big change in this method is there is a parameter sum in the method signature, this sum will store the calculated result at each recursive call. So this value can be directly returned when the recursion call stops. If n is set to 200000 and run the tail recursion version method, there will be no StackOverflowError now.

In simple, the main difference between the traditional recursion and tail recursion is when the actual calculation takes place. In traditional recursion, calculation will happen after the recursion call while the calculation will occur before the recursion call in tail recursion.

3. Reference

https://maxglassie.github.io/2017/08/24/tail-recursion.html

https://www.pixelstech.net/article/1474689232-Traditional-recursion-vs-Tail-recursion

https://www.geeksforgeeks.org/tail-recursion/

https://ledgku.tistory.com/37

https://bozeury.tistory.com/entry/%EA%BC%AC%EB%A6%AC-%EC%9E%AC%EA%B7%80-%EC%B5%9C%EC%A0%81%ED%99%94Tail-Recursion