tail recursion

A recursive function call at "the very end" of a function is called tail recursive.

More formally, the value of a tail recursive call is immediately returned by the caller.

Tail recursive calls can always be optimised into simple jumps -- they are not recursive at all! This is used by the language Scheme, which uses tail recursion to express iteration.

T = T = talk mode

tail recursion n.

If you aren't sick of it already, see tail recursion.

--Jargon File, autonoded by rescdsk.

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.

It is interesting to note that without tail recursion, functional programming loses most of its charm. Pure functional languages need recursion to express a lot of common structures. Consider a typical pseudo-C event-handling loop:

for(;;) {
  event = waitForEvent();

  /* do something with the event */
}

Now, the way to write infinite loops in functional programming is through recursion (somewhat inaccurate example):

function handleEvent(event) :
  ( do something with the event )
  handleEvent(getNextEvent())

Now, as you might remember, every function call needs some memory. Notice that this loop will need more memory for each event it processes; which might be acceptable on most recursive algorithms, but an event-handler which runs without the tail recursion optimization will eventually run out of memory.

Tail recursion is particularly useful in programming in Scheme (a dialect of LISP). I do not know other LISP variants, so I cannot speak for them.

Because of the complexity of writing some recursive functions, they often end up being deep-recursive. Recall that tail-recursive algorithms are frequently defined as those where the value of the recursive call is equivalent to the value of the entire function. Therefore, those where some work is done on the recursive call before passing it up the stack are deep-recursive. Take the classic example of the factorial algorithm:

(define factorial
    (lambda (n)
        (if (= n 0)
            1
            (* n (factorial (- n 1))))))

Notice how the result of the recursive call is then multiplied by n. If you picture the stack, this algorithm is getting more complex every time you recurse, and after the algorithm reaches the base case, it still needs to multiply out that value by all of the preceding values of n. This is a big loss of efficiency when you compare it to:

(define factorial
    (lambda (n answer)
        (if (= n 0)
            answer
            (factorial (- n 1) (* answer n)))))

Although there is now an extra variable, this is now properly tail-recursive, as once we reach the base case and return the answer variable, we're done. Each previous recursive call just passes the value it receives back up the stack.

And if that's not enough, the Scheme interpreter is smart enough to recognize proper tail recursion and converts it into actual iteration when it's evaluating. This can result in a huge gain in efficiency, as well as reducing the amount of memory needed to evaluate these algorithms and greatly reducing the amount of time that that memory needs to be used.

---

Source: Professor Richard Salter of Oberlin College