Insight 21.9.1.
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.
Section 21.9 Tail Recursion
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:
void countdown(int n) {
if (n == 0) {
cout << "Blastoff!" << endl;
} else {
cout << n << endl;
countdown(n - 1); // recursive call
}
}
Our other recipes have not been tail-recursive, as we always do something to build on the answer produced by the recursive call:
int factorial(int n) {
if (n == 0) {
return 1;
} else {
// get answer, then multiply by n before returning
return n * factorial(n - 1);
}
}
The advantage of tail-recursive functions is that they can be optimized by the compiler to avoid increasing the call stack depth, thus preventing stack overflow errors for deep recursions. Essentially, the compiler can “cheat” and just keep using the same stack frame for each recursive call. If the call to
factorial(5) does not need to do anything once factorial(4) is done producing an answer, there is no need to keep a stack frame around for it. We can just overwrite it with the data for factorial(4). Then we can wipe that out and reuse the space for factorial(3). And so on...
But how do we make the function tail recursive?
factorial(4) counts on being able to ask factorial(3) for its answer and then factorial(4) produces the answer including 4. To make it tail-recursive, we need factorial(4) to give all the information factorial(3) needs to get the final answer.
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”.
int factorial(int n, int accumulator);
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. But when we reach n == 0, we already should have a final result to return.
Here is 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. We also have a non-recursive function to kick start the recursive process with an accumulator of 1.
It is harder to see what is getting returned from each level of recursion, as we do not store the result at each level before returning it to the next (that would not be tail recursive!). However, you can see that the base case returns the answer 24 and every recursive level just returns that same answer.
Checkpoint 21.9.1.
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.
You have attempted of activities on this page.
