Head and tail recursion

Here are two recursive functions that make exactly the same calls. The only difference is one line: down prints n before it calls itself, and up prints n after.

void down(int n)                void up(int n)
{                               {
    if (n == 0)                     if (n == 0)
        return;                         return;
    printf("%d ", n);               up(n - 1);
    down(n - 1);                    printf("%d ", n);
}                               }

Before you play it, guess what down(3) and up(3) print. Then watch both run side by side, one call at a time.

Before the call or after it

down(3) prints 3 2 1. up(3) prints 1 2 3. The calls are the same, four of them on each side, n = 3, 2, 1 and 0, and the stacks grow and shrink at the same moments. What differs is when each call does its work.

down prints first and calls second. So down(3) prints 3 before down(2) even exists, then down(2) prints 2, and so on. The numbers come out on the way down, in the order the calls are made.

up calls first and prints second. up(3) cannot print until up(2) has returned, and up(2) cannot print until up(1) has returned. The first call to print is the last one made, up(1), as soon as up(0) returns. The numbers come out on the way back, in reverse order. Watch the right row in the clip: it stays empty while the stack grows, and it fills only as the cards leave.

Look at the left side as the cards leave. Each down card goes without doing anything: its call was the last thing it had to do. That empty return trip is the key to the second half of this page.

The code and its cost

Tail calls and head recursion

A tail call is a call that is the last thing a function does: when it returns, the caller has nothing left to do but return too. down(n - 1) is a tail call. A function whose recursive call is a tail call is tail recursive.

up is the other kind. Its work, the printf, comes after the call. This is often called head recursion: the call comes at the head of the work, and the work happens on the way back.

Be careful with the word “last”. Here is the factorial from Recursion (4.1), written in one line:

return n * factorial(n - 1);

The call is on the last line, but it is not a tail call. After factorial(n - 1) returns, there is still a multiplication to do. The same is true of return n + sum_to(n - 1);. A call is a tail call only if nothing at all happens after it.

Turning a tail call into a loop

When a call is the last thing a function does, the caller’s frame is not needed any more. Nothing in it will be read again. So instead of making a new frame for down(n - 1), we can reuse this one: change n to n − 1 and go back to the top. That is a loop:

void down_loop(int n)
{
    while (n > 0) {
        printf("%d ", n);
        n = n - 1;
    }
}

Compare the two at the end of the clip. down(3) held 4 frames at its deepest point, one for each n from 3 down to 0. down_loop(3) prints the same 3 2 1 with one frame, and its n changes in place. In general down(n) needs n + 1 frames and down_loop(n) needs one.

up cannot be turned into a loop this way. Each frame still has a printf to do after its call returns, with its own n, so every frame must wait. To print 1 2 3 with a loop you would count up instead, which is a different function.

What the compiler does

You do not always have to write the loop yourself. An optimising compiler can turn a tail call into a jump back to the top of the function. I checked what gcc 13 makes of order.c, by listing the calls in the machine code of each function:

At -O2, down’s call to itself has become a jump, so down runs in one frame, like down_loop. up still calls itself, because its work after the call needs each frame. At -O0, the setting a debugger uses, every call makes a frame.

So “recursion always costs more memory than a loop” is not quite true. A tail-recursive function built with optimisation can cost the same as the loop. But C does not promise it: the standard says nothing about it, and a build without optimisation keeps every frame. If the depth could be large, write the loop.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic order.c -o order
./order

It prints three lines: 3 2 1, 1 2 3, 3 2 1. To see the jump, build with gcc -std=c11 -O2 -c order.c and list the machine code with objdump -d order.o.

Worked example

Both at once. What does this print for both(3)?

void both(int n)
{
    if (n == 0)
        return;
    printf("%d ", n);
    both(n - 1);
    printf("%d ", n);
}

Each call prints its n on the way down and again on the way back. On the way down: 3, 2, 1. Then both(0) returns, and on the way back: 1, 2, 3. So both(3) prints 3 2 1 1 2 3. The second printf comes after the call, so this is not tail recursive.

Factorial as a tail call. The factorial of 4.1 multiplies on the way back. We can make it multiply on the way down instead, by carrying the product so far in a second argument, acc (an accumulator):

int fact_acc(int n, int acc)
{
    if (n == 0)
        return acc;
    return fact_acc(n - 1, acc * n);
}

Start it with fact_acc(5, 1). Each call multiplies before it calls, so the work is done on the way down:

The sixth call, n = 0, returns acc, which is 120, and every call above it passes that 120 straight back. The call fact_acc(n - 1, acc * n) is a tail call: nothing happens after it. Built with -O2, gcc removes it completely, and fact_acc has no calls left in its machine code. Built with -O0, it takes 6 frames.

Counting frames. down(1000) makes 1,001 calls, and at -O0 all 1,001 frames are on the stack at once, at the deepest point. down_loop(1000) uses one frame for the whole run. up(1000) also needs 1,001 frames at -O0. At -O2, gcc folds four calls into one, so it takes 250 frames. That is still one frame for every few calls: the call in up is not a tail call, so the stack still grows with n.

Where it’s used

Printing a list backwards. A linked list can only be walked from front to back. To print it from back to front, use the head form: print the rest of the list first, then this node’s key. Reversing a list does exactly this with print_backwards.

Languages without loops. Some programming languages have no while or for at all. They repeat things by recursion, and their rules promise that a tail call does not use a new frame, so a tail-recursive function runs like a loop. Scheme is one such language.

Compilers. Removing tail calls is a standard optimisation, as the table above shows for gcc. It saves both the frames and the time spent making them.

Trees. Visiting a tree’s nodes before or after their children gives different orders, for the same reason down and up do. Tree traversals (12.3) are built on this.

Reference card

Platform: C11, gcc 13 on x86-64 Linux. The cards in the picture show names and values only.