Traditional recursion vs Tail recursion

Recursion is a frequently adopted pattern for solving some sort of algorithm problems which 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.

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

The same can be done using traditional recursion way.

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

There is a saying that every recursion problem can be solved using loop with the cost of writing more difficult to understand code. 

Everything is fine now. But if the recursive calculations become too many, there is a potential of Stackoverflow issue. This is because when every method is invoked with 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 intermediate value stored for each recursive call until the stop condition reaches. Unfortunately, a modern interpreter or virtual machine will often have stack limit which limits the number of stacks created. If this limit is exceeded, there will be StackOverflowError or similar happening.

Let's take above 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)

In this case, recursion(traditional recursion) may be considered as a bad idea as it will make the program fail unexpectedly. In fact, there is another recursion pattern which can be adopted to resolve the StackOverflowError -- Tail recursion. A 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. 

The tail recursion of the method would look like

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.