Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
Tail Recursion
A recursive function is said to be tail recursive if all recursive calls within it are tail recursive. A recursive call is tail recursive when it is the last statement that will be executed within the body of a function and its return value is not a part of an expression. Tail-recursive functions are characterized as having nothing to do during the unwinding phase. This characteristic is important because most modern compilers automatically generate code to take advantage of it.
When a compiler detects a call that is tail recursive, it overwrites the current activation record instead of pushing a new one onto the stack. The compiler can do this because the recursive call is the last statement to be executed in the current activation; thus, there is nothing left to do in the activation when the call returns. Consequently, there is no reason to keep the current activation around. By replacing the current activation record instead of stacking another one on top of it, stack usage is greatly reduced, which leads to better performance in practice. Thus, we should make recursive functions tail recursive whenever we can.
To understand how tail recursion works, let's revisit computing a factorial recursively. First, it is helpful to understand the reason the previous definition was not tail recursive. Recall that the original definition computed n! by multiplying n times (n - 1)! in each activation, repeating this for n = n - 1 until n = 1. This definition was not tail recursive because the return value of each activation depended on multiplying n times the return value of subsequent activations. Therefore, the activation record for each call had to remain on the stack until the return values of subsequent calls were determined. Now consider a tail-recursive definition for computing n!, which can be defined formally as:
This definition is similar to the one presented earlier, except that it uses a second parameter, a (initially set to 1), which maintains the value of the factorial computed thus far in the recursive process. This prevents us from having to multiply the return value of each activation by n. Instead, in each recursive call, we let a = na and n = n - 1. We continue this until n = 1, which is the terminating condition, at which point we simply return a. Figure 3.4 illustrates the process of computing 4! using this approach. Notice how there is no work that needs to be performed during the unwinding phase, a signature of all tail-recursive functions.
int facttail(int n, int a)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (n == 1)
return a;
else
return facttail(n - 1, n * a);
}
Back to top
