Getting a Hang of Recursion

The base case stops only the call that reaches it

The function trace follows one simple rule: print a down message, make a call with a smaller n, then print an up message. When n is 0, the base case prints stop and returns immediately. That return ends trace(0), but it does not erase the calls that were waiting for trace(0) to finish.

void trace(int n) {
    if (n == 0) {
        cout << "stop" << endl;
        return;
    }

    cout << "down " << n << endl;
    trace(n - 1);
    cout << "up " << n << endl;
}

static void trace(int n) {
    if (n == 0) {
        System.out.println("stop");
        return;
    }

    System.out.println("down " + n);
    trace(n - 1);
    System.out.println("up " + n);
}

Starting with trace(3), the first call has n equal to 3, so it prints down 3 and calls trace(2). That call prints down 2 and calls trace(1). Then trace(1) prints down 1 and calls trace(0). The call with n equal to 0 prints stop and returns without making trace(-1).

At the moment trace(0) returns, trace(1), trace(2), and trace(3) have not finished. Each one has already printed its down line and is waiting at its recursive call. The up lines still belong to those earlier calls, so they can run after the deeper call returns.

A recursive call pauses its caller instead of replacing it

When trace(3) calls trace(2), the call with n equal to 3 does not disappear. Its current position is remembered: it has finished printing down 3 and must continue with print up 3 after trace(2) returns. The same thing happens when trace(2) calls trace(1), and when trace(1) calls trace(0).

A call frame is the stored state for one active call. For this function, a frame stores that call's value of n and the location to continue from. While trace(0) runs, three separate frames store 3, 2, and 1. Their pending statements are print up 3, print up 2, and print up 1.

The top frame is the call currently running. When trace(0) returns, trace(1) becomes the active call again and continues with its pending up line. After trace(1) returns, trace(2) resumes, and after trace(2) returns, trace(3) resumes. A deeper call therefore adds a new frame instead of replacing the caller.

Code before and after the recursive call runs in opposite phases

The down statement appears before the recursive call, so it runs while calls are moving deeper: down 3, down 2, then down 1. The base case then prints stop. The up statement appears after the recursive call, so it waits for the return phase and runs in the opposite order: up 1, up 2, then up 3.

The first paused caller to resume is trace(1), not trace(3). It is the most recent caller of trace(0), so it is the first one reached when the deepest call returns. This last-in, first-out order is why the values in the up lines rise from 1 back to 3.

A call-by-call table makes the execution order mechanical

You can trace the function without guessing by recording the active call, its current n, the next action, and any output from that action. Making a deeper call moves to a new active frame. Returning moves back to the paused frame and lets its pending statement run.