tail recursion (idea)

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.