Before discussing tail call recursion, let’s revise normal recursion. In short recursion is a coding pattern where a functions calls itself. we'll take a simple example.
function main() {
return naturalSum(3);
}
function naturalSum(int num) {
if(num===1) return 1;
return num + naturalSum(num-1);
}
main();
This function takes an integer num and returns the sum of all natural numbers till num. To understand the execution of this program, you need a good understanding of the call stack.
Let's see how the call stack will grow in our program
Each instance of naturalSum is waiting in the call stack for it's subsequent call to be resolved. So the stack will keep growing with increasing value of num. At last when value of num is 1, our base condition of recursion is met, stack will stop growing and start resolving the frames.
Space complexity of our program is O(n), Which is not very efficient for this simple problem. if value of num is too high, we'll get the notorious stack overflow error. I know some of you are thinking we can use loops instead, and you're right, but sadly this article is not about loops.
Now let's rewrite our program
function main() {
let currentSum = 0;
return naturalSum(3, currentSum);
}
function naturalSum(num, currentSum) {
if(num===0) return currentSum;
return naturalSum(num-1, num+currentSum);
}
We've added another parameter currentSum in the definition of our function. With each recursive call to our function we'll keep updating it's value by adding num to it's current value.
Let's go through the call stack again.
And now the shrinking call stack after num reaches 0.
There're some obvious difference from the first flow here, If you look at the shrinking call stack diagram of previous code, you'll notice each stack frame of naturalSum call is returning different value, wherein with the new code each stack frame of naturalSum is returning the same integer (6), which is also expected return of the first naturalSum call. This brings us to tail call recursion.
What is tail call recursion?
Tail call recursion is a special case of recursion where recursive call is the last statement of the function. That means there's no computation left after the recursive statement.
If we talk about this statement return num + naturalSum(num-1);, there's still the addition of num pending after calling naturalSum(n-1);. That's why our first program was not tail recursive.
Optimisation
Some of you may argue if every stack frame in tail call is returning the same value, what's the point of holding onto all those stack ? what's the point of storing all that data ?
Tail call optimisation
And that's exactly what compiler/interpreter designers argued. Compilers identify if the called function is tail call recursive or not, and if it is, instead of adding a new stack frame on top, top frame will simply get replaced with the new frame.
This brings down the space complexity from O(n) to O(1). This way of optimizing the call stack space is called tail call recursion optimisation.
Tail call elimination
There's another way of avoiding these unnecessary stack frames, which is to simply replace the recursion with loops. that's called tail call elimination.
Keep in mind both these technique have prerequisite that our function should be tail call recursive.
Although I took the examples of JavaScript above, not all implementations of JavaScript engines optimize tail calls.
Generally functional languages like Scala use these optimizations due to the nature of their high function centric coding patterns.
Now question is if the optimizations are so good why don't every language uses it ? For one, stack frames are getting lost, which results in compact but incomplete stack trace. which is not always ideal. You can read a similar issue that is discussed here: https://github.com/ocaml/ocaml/issues/6047
Some compilers use the information of the complete stack down the line, so it becomes difficult to implement it. And at last it's not something which we can't do without, it's easy to convert a tail recursive function into a loop.