A tail-recursive function is one where the recursive call is the last operation in the function, no work is done other than returning the answer produced by the recursion. Our countdown function was tail recursive. No work happens in it after the recursive call to countdown:
In our other recursive recipes, we have always done something to build on the answer produced by the recursive call. For example, our factorial function takes the answer produced by the recursive call and multiplies it by the current number:
Why would we care if our function is tail recursive? In a function that is not tail recursive, we have to keep track of the state of each stack frame while we wait for the recursive call to return. factorial(5) needs to store its copy of n while waiting on factorial(4). factorial(4) needs to store its copy of n while waiting on factorial(3). And so on. If we have a very deep recursion, we can run out of stack space and get a stack overflow error.
In a tail recursive function, there is no need to remember anything in the current stack frame. All the work at that level is already done. So, given a tail recursive function, the compiler can “cheat” and reuse the same stack frame for each recursive call. When factorial(5) calls factorial(4) a new stack frame won’t be created. Instead the data for the new call will just overwrite the current stack frame.
This depends on the compiler being smart enough to recognize that the function is tail recursive and optimize it. Some compilers will do this optimization, but not all. In functional programming languages like Scheme that rely heavily on recursion, the language specification often requires that tail recursion be optimized. In C++, the compiler is allowed to optimize tail recursion, but it is not required to do so.
But how do we make the function tail recursive? factorial(4) counts on being able to ask factorial(3) for its answer and then produces its own answer based on that. To make it tail-recursive, we need to change where the work happens. We need factorial(4) to pass all the information needed to calculate a final answer to factorial(3) and count on it to return the final answer. factorial(3) will in turn have to pass all the information needed to calculate a final answer to factorial(2).
As always when we want to pass more information from one recursive call to the next, that means a new parameter. We will call this parameter the accumulator as it will accumulate the “answer so far”.
Now if we start with factorial of 4, it will call factorial(3, 4) to say “Hey, you need to calculate 3! and multiply that by 4.”. factorial(3), will take the 4, multiply it by 3, and then call factorial(2, 12) to say “Hey, you need to calculate 2! and multiply that by 12.”. Eventually we will call factorial(0, 12) to say “Hey, you need to calculate 0! and multiply that by 12.”. Factorial of 0 is still our base case. Only now, instead of returning 1, it returns the final answer. The call sequence for an initial input of 4 looks like:
Tail recursion focuses on doing work on the way down the recursion stack. Non-tail recursive algorithms do work on the way back out of the recursion calls.
Here is an implementation of that function. Note that it does the work to calculate newAccumulator (“the answer so far”) before the recursive call and then hands that value off to the next call. The result of trying to calculate something like factorial(20000) will be incorrect as we overflow the integer being used. But there is no stack overflow error!
Construct a tail recursive version of countZeros. We will add a parameter to keep track of the current count of zeros so that all the work can be done on the way down the recursion stack.
