Tail recursion is a special case of normal
recursion in which the
environment or
stack frame associated with each instance of the routine can be re-used by the recursive call at the end of the routine (because it is the last thing to be done by the parent routine).
First, the canonical example of non-tail recursion (in C):
int factorial(int n)
{
if(n <= 1)
return 1;
return n*factorial(n-1);
}
Note that the factorial routine needs to "remember" the value of n so that it can multiply by it when the recursive call returns.
Now, a truly tail-recursive version:
int factorial_tail(int n, int accumulator)
{
if(n <= 1)
return accumulator;
return factorial_tail(n-1, accumulator * n);
}
int factorial(int n)
{
return factorial_tail(n, 1);
}
Note that factorial_tail has already done all relevant calculations by the time it does the recursive call, so it can discard its own values of n and accumulator.
This leads us to the crucial transformation that shows that tail recursion is equivalent to a standard while() loop:
int factorial_goto(int n, int accumulator)
{
beginning:
if(n <= 1)
return accumulator;
accumulator *= n;
n -= 1;
goto beginning;
}
One should convince oneself that factorial_tail and factorial_goto are identical in behavior; from there, one can easily convert the goto to a while loop:
int factorial_while(int n, int accumulator)
{
while(n > 1) {
accumulator *= n;
n -= 1;
}
return accumulator;
}
This is the essential transformation between
iteration and
recursion that is discussed in
computer science classes.
A conforming implementation of the
Scheme dialect of
LISP must implement tail recursion in terms of this transformation.
Tail-recursion is a special case of a more general transformation called tail-call optimization; essentially, any C function ending with the pattern return foo(args); can translate to a goto to foo, rather than introducing an extra stack frame.