Trace a Recursive Call Through the Call Stack

Work before the call runs on the way down, and work after it runs on the way back up.

Tracing a recursive function means following its calls on the call stack, the stack of frames that holds one frame per unfinished call, and writing down what each call does before and after the call inside it. This card covers that procedure on a function that prints on both sides of its recursive call, and why the second half of its output comes out reversed.

The goal is the exact output of show(3). The base case, the input a recursive function answers without calling itself, is n = 0, and it does nothing. Every other call prints a line, calls show(n - 1), and prints a second line once that call has returned.

before_after.pypy

def show(n):
    if n == 0:
        return
    print("before", n)
    show(n - 1)
    print("after", n)


show(3)

Before the steps: what does show(3) print, line by line?

A run printed the three before lines counting down, then the three after lines counting up.

text

before 3
before 2
before 1
after 1
after 2
after 3

The method is to keep two things on paper: the stack, top frame first, and everything printed up to that point. Each step is one event: a call that starts, or a call that returns and lets the frame beneath it carry on. An instrumented copy of the function printed both after every event:

The stack and the output after each event in show(3)

show(3) runs its first half

3 is not the base case, so the call prints its before line and calls show(2). Its after line has to wait.

text

stack, top first: show(3)
printed: before 3

show(2) runs its first half

A new frame goes on top, prints, and calls show(1).

text

stack, top first: show(2) show(3)
printed: before 3 | before 2

show(1) runs its first half

The same happens one level deeper. Three frames are now paused, each in the middle of its body.

text

stack, top first: show(1) show(2) show(3)
printed: before 3 | before 2 | before 1

show(0) is the base case

n is 0, so the call returns at once and prints nothing. This is the deepest point, with four frames.

text

stack, top first: show(0) show(1) show(2) show(3)
printed: before 3 | before 2 | before 1

show(1) finishes

The top frame is popped. show(1) was paused on its recursive call, so it carries on from the next line and prints after 1. The first after line belongs to the deepest call that prints.

text

stack, top first: show(1) show(2) show(3)
printed: before 3 | before 2 | before 1 | after 1

show(2) finishes

show(1) returns, and show(2) prints its after line.

text

stack, top first: show(2) show(3)
printed: before 3 | before 2 | before 1 | after 1 | after 2

show(3) finishes

The first call is the last to finish. Once it returns, the stack is empty.

text

stack, top first: show(3)
printed: before 3 | before 2 | before 1 | after 1 | after 2 | after 3

The order follows from the stack. Work written before the recursive call runs as the calls go down, so it happens in the order the calls were made: 3, 2, 1. Work written after the call runs as the calls return, and a stack returns its newest frame first, so it happens in the reverse order: 1, 2, 3.

The common mistake is to stop tracing at the base case, as though a call ends when it makes its recursive call. It does not: it pauses there, and the rest of its body runs later. A function that prints only after its call, with nothing before it, prints 1 2 3 for show(3), not 3 2 1.

← → move through sections and cards