Recursion in C: trace calls, returns and local variables

You put a printf after a recursive call and the numbers come out in reverse order. Yet there's no loop counting upward. To explain the output, you need to keep track of the calls that haven't finished.

In what order do the printf statements run?

The first printf runs before descending; the second waits for walk(n - 1) to return. This program is short enough to follow line by line.

#include <stdio.h>
static void walk(int n){    if (n <= 0) {        printf("base %d\n", n);        return;    }    printf("before %d\n", n);    walk(n - 1);    printf("after %d\n", n);}
int main(void){    walk(2);    return 0;}

$ gcc -std=c17 -Wall -Wextra -Werror -O0 -g walk.c -o walk$ ./walkbefore 2before 1base 0after 1after 2

walk(2) prints before 2, then calls walk(1). Its last printf still needs to run. walk(1) does the same with walk(0). That call reaches the base case and returns, allowing walk(1) to print after 1 and finish. Finally, walk(2) resumes and prints after 2.

The phrase "on the way back up" describes this return order. Execution doesn't rewind the lines that already ran or restart the function from the beginning.

Which call is active at each step?

Only one call in our program executes an instruction at a time. The others are waiting or have already finished. Each snapshot below is taken just before the printf shown in next; the cells keep the same identity throughout the trace.

Cells marked "finished" retain the history. They no longer represent accessible variables in an active function call.

Why does n become 1 and then 2 again?

Those values were never overwritten. The expression n - 1 computes an argument for the next call without assigning anything in the caller. At the base case, the calls to walk have three distinct instances of the parameter:

This diagram shows the walk calls, leaving out main and library frames. The call stack is a useful model for keeping track of pending work. Machine frame details can change with optimization; the observable order of this program still follows its statements.

A static local variable would be shared across calls. The parameter int n here isn't static. For the connection to object lifetime, see Stack and heap in C. The explanation of passing values and pointers also covers why changing an ordinary parameter doesn't directly change the caller's variable.

What changes if walk(n - 1) becomes walk(--n)?

--n first decreases the current call's parameter and then passes that value to the next call. The descending arguments are still 1 and 0, but the waiting calls have changed their own n too. Replace just that expression to see the difference:

$ sed 's/walk(n - 1)/walk(--n)/' walk.c > changed.c$ gcc -std=c17 -Wall -Wextra -Werror changed.c -o changed$ ./changedbefore 2before 1base 0after 0after 1

In the modified version, the call that started with 2 has already decreased its parameter to 1 before waiting. The call that started with 1 has decreased it to 0. Their final printf statements therefore print 0 and then 1. Passing by value still works; the caller's expression has introduced a mutation.

Keep n - 1 when you want to pass a smaller value while preserving the current level for the return path. By contrast, n-- passes the value before decrementing it, so the next call receives the same positive number again. With our base case, that doesn't move the descent toward zero.

Why must the base case come before the next call?

It must prevent another call when the input is already a terminal case. Here, n <= 0 prints one base line and leaves the current call before any subtraction. Thus walk(0) prints only base 0, and walk(-1) prints only base -1.

For a positive input, n - 1 moves each call closer to zero. Both properties matter: a stopping case and progress toward it. Having a condition in the source isn't enough if the arguments move away from it.

The return in walk(0) doesn't leave walk(1) or main. It resumes the call site that invoked it. The work still pending in the parent calls accounts for the after lines.

descend

Turn this traversal into notifications in descend: call on_enter on the way down and on_leave on the way back up. Your function must not print, and either callback may be NULL. Its base case produces no notifications, unlike the base line in our demonstration.

Open the exercise

How can you trace another recursive function on paper?

Record each call separately, including its arguments and the next instruction to execute when it resumes. Stop descending at the base case, then finish the most recent call first. Add an output line only when execution reaches its statement.

For walk(3), predict the output before changing main: before runs from 3 down to 1, followed by base 0 and after from 1 up to 3. Check it in the visualizer or with gdb(1). If a function contains several recursive calls, record which call comes next as well; a column of values alone no longer captures the pending work.

Frequently asked questions