Introduction to Recursion: Calls Pause, Then Resume

A recursive call starts a new invocation without erasing the current one

A recursive function calls itself, but the current invocation does not disappear. It pauses at the recursive call and waits for the new invocation to finish. Each invocation has its own value of n and its own place to continue. In trace(3), the invocation with n = 3 prints its entry message, calls trace(2), and pauses before it can print its leave message.

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

    cout << "enter " << n << "\n";
    trace(n - 1);
    cout << "leave " << n << "\n";
}

After trace(3) calls trace(2), a new invocation starts with n = 2. The old invocation still remembers n = 3 and the next statement it must execute: cout << "leave " << n. Nothing after the call has run yet, but nothing after the call has been lost either.

The base case stops the chain before another recursive call begins

The calls move from trace(3) to trace(2), then trace(1), then trace(0). When n is 0, the condition n == 0 is true. trace(0) prints "stop" and returns immediately. It does not call trace(-1), because the base case decides that no deeper invocation is needed.

trace(3) -> trace(2) -> trace(1) -> trace(0)

trace(0): prints "stop", then returns

A base case is an ordinary condition in the function. It does not have special powers beyond choosing a different path: print "stop" and return instead of making the recursive call. Without that condition, the function would keep trying to create a deeper invocation.

A paused invocation resumes after the deeper invocation returns

When trace(0) returns, the most recently paused invocation is trace(1). It resumes at the statement after trace(0), so it prints "leave 1" and returns. Then trace(2) resumes and prints "leave 2", followed by trace(3), which prints "leave 3". The leave messages appear in reverse order because the last invocation to pause is the first one able to resume.

enter 3
enter 2
enter 1
stop
leave 1
leave 2
leave 3

The exact location of the recursive call explains the output. Each invocation pauses immediately after that line. trace(1) is closest to trace(0), so it is resumed first. Its leave statement runs before trace(2) can resume, and trace(2)'s leave statement runs before trace(3)'s. The caller is not erased, it is waiting for the call it made.

The recursive step must move every invocation toward the base case

The recursive step in trace is trace(n - 1). Starting from n = 3, each new invocation receives a smaller value: 3, then 2, then 1, then 0. This movement guarantees that the base case can eventually become true. A recursive function needs both a condition that stops and a recursive step that moves its input toward that condition.

cout << "enter " << n << "\n";
trace(n - 1);
cout << "leave " << n << "\n";

If the recursive step is changed to trace(n), trace(3) calls another trace(3), which calls another trace(3), and so on. Every invocation still has n = 3, so none reaches n == 0. The calls continue creating paused invocations until the call stack runs out of space. In that case, the function never reaches the leave statement of any paused invocation.