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.