A girl and a robot thinking together

Think together · Start with a little story

A girl uses three task cards to draw recursion. She adds a card when a call goes deeper and removes the top card when it returns.

Lay out the process

Follow the steps, then explain them in your own words
  1. Enter f(3)Add a card to the stack
  2. Enter f(2)Add another card
  3. Enter the smallest taskStop adding cards
  4. ReturnRemove cards one at a time

Each active recursive call must remember where to return and what its current level still needs.

The top of the stack is the call currently running; the calls below it are waiting. Watching the stack’s height helps you see how deep the recursion goes.

See both the calls and the returns

The task cards go from the bottom of the stack on the left to the top on the right. The rightmost card is the call currently running.

Step 1 · Enter factorial(3)
f(3)

This call must compute 3 × f(2), so it waits for f(2).

Step 2 · Enter factorial(2)
f(3) waitingf(2)

This call must compute 2 × f(1), so it adds another call.

Step 3 · Continue to the base case
f(3) waitingf(2) waitingf(1) waitingf(0) = 1

f(0) returns 1 directly, without adding another call.

Step 4 · Return to factorial(1)
f(3) waitingf(2) waitingf(1) = 1

Compute 1 × 1, get 1, and return.

Step 5 · Return to factorial(2)
f(3) waitingf(2) = 2

Compute 2 × 1, get 2, and return.

Step 6 · Return to factorial(3)
f(3) = 6

Compute 3 × 2, get 6. This call is complete.

01Start with f(3)

void f(int n) {
    if (n == 0) {
        return;
    }

    f(n - 1);
}

Calling f(3) leads to calls to f(2), f(1), and f(0).

02How does the call stack grow one level at a time?

Step 1

f(3)

→
Step 2

f(2)
f(3)

→
Step 3

f(1)
f(2)
f(3)

Calling f(0) adds one more level.

03Is n the same variable at every level?

No. Every function call has its own parameter object.

f(3)

n = 3

f(2)

n = 2

f(1)

n = 1

f(0)

n = 0

While these calls are active at the same time, each one keeps its own state.

04Why does the previous call “wait”?

When f(3) calls f(2), f(3) has not finished yet.

It must wait for f(2) to finish and return before it can continue with code after the call.

05What happens after the base case?

f(0) returns↑Back to f(1)↑Back to f(2)↑Back to f(3)

The call stack now shrinks one level at a time from the top.

06Is a call-stack diagram an exact picture of memory?

No. It is an important model of program execution and also reflects a common implementation approach.

The compiler, platform ABI, and optimizations determine what each actual stack frame contains, how it is aligned, and which variables may be kept in registers.

What have you learned?

  • Every recursive call has its own call state.
  • Common implementations organize active calls on a call stack.
  • Each recursive call has its own parameters and local variables.
  • A deeper call must finish before execution can return to the previous call.
  • After reaching the base case, calls return one by one in reverse order.

Next: How Does Recursion Return One Level at a Time?

Your turn to try

When a call returns, should you remove the bottom card or the top one?

Ready? Open to see the explanation

The top one. Calls below it are not finished yet; they must wait for the result to come back.