# Where Do the Waiting Calls Wait? The Call Stack

Trace any recursive function by hand, and see why recursion that goes too deep runs out of room: how a program keeps every waiting call's own values and the way back to it, which a single variable or a single bookmark can't do.

Apprentice · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Trace a recursive function's calls on the call stack, frame by frame
- Explain what a stack frame holds and why each waiting call uses memory

## Key takeaways

- Every function call gets a stack frame: its own copy of its parameters and variables, and the spot to go back to.
- Frames pile up on the call stack as calls go in, and come off, newest first, as each call finishes: last in, first out.
- One shared variable would be overwritten by every call, and one bookmark couldn't go back more than one level: each waiting call needs a frame of its own.
- Recursion n calls deep keeps n frames waiting at once, so it uses O(n) memory as well as O(n) time.
- The call stack is small, so too many frames waiting at once is a stack overflow, the folder tool's crash.

**Before this:** *The Folder Tool That Never Stopped: Base Cases* crashed when the call stack ran out of room. This lesson opens it up and looks at what it holds.

The folder tool printed *Beach Trip* before *2024*, and *Photos* last, each with its own total. The crash report from the customer's drive named `folder_size` over and over, newest first. Both come from the same place. Here's the smallest program that shows it: a countdown that prints a line when each call starts and another when it finishes.

```csharp
void Countdown(int number)
{
    Console.WriteLine("Starting the call with " + number);
    if (number == 0)
    {
        Console.WriteLine("Liftoff!");
    }
    else
    {
        Countdown(number - 1);
    }
    Console.WriteLine("Finishing the call with " + number);
}

Countdown(3);
```

```text
Starting the call with 3
Starting the call with 2
Starting the call with 1
Starting the call with 0
Liftoff!
Finishing the call with 0
Finishing the call with 1
Finishing the call with 2
Finishing the call with 3
```

```java
void countdown(int number) {
    IO.println("Starting the call with " + number);
    if (number == 0) {
        IO.println("Liftoff!");
    } else {
        countdown(number - 1);
    }
    IO.println("Finishing the call with " + number);
}

void main() {
    countdown(3);
}
```

```text
Starting the call with 3
Starting the call with 2
Starting the call with 1
Starting the call with 0
Liftoff!
Finishing the call with 0
Finishing the call with 1
Finishing the call with 2
Finishing the call with 3
```

```python
def countdown(number):
    print(f"Starting the call with {number}")
    if number == 0:
        print("Liftoff!")
    else:
        countdown(number - 1)
    print(f"Finishing the call with {number}")


countdown(3)
```

```text
Starting the call with 3
Starting the call with 2
Starting the call with 1
Starting the call with 0
Liftoff!
Finishing the call with 0
Finishing the call with 1
Finishing the call with 2
Finishing the call with 3
```

```javascript
function countdown(number) {
  console.log(`Starting the call with ${number}`);
  if (number === 0) {
    console.log("Liftoff!");
  } else {
    countdown(number - 1);
  }
  console.log(`Finishing the call with ${number}`);
}

countdown(3);
```

```text
Starting the call with 3
Starting the call with 2
Starting the call with 1
Starting the call with 0
Liftoff!
Finishing the call with 0
Finishing the call with 1
Finishing the call with 2
Finishing the call with 3
```

```typescript
function countdown(number: number): void {
  console.log(`Starting the call with ${number}`);
  if (number === 0) {
    console.log("Liftoff!");
  } else {
    countdown(number - 1);
  }
  console.log(`Finishing the call with ${number}`);
}

countdown(3);
```

```text
Starting the call with 3
Starting the call with 2
Starting the call with 1
Starting the call with 0
Liftoff!
Finishing the call with 0
Finishing the call with 1
Finishing the call with 2
Finishing the call with 3
```

Read the *Finishing* lines. They come out in reverse, 0, 1, 2, 3, and each one has the right number. That's a puzzle. There's only one `number` in the code, and the last call to set it set it to 0. So how does the call with 3, which finishes last, still know its number was 3? And when the call with 0 is done, how does the program know to go back to the call with 1, then 2, then 3?

## What would you try?

Imagine you're the computer, and you have to make this work. How would you keep track?

**One `number` for the function.** Every call writes its number into the same box: 3, then 2, then 1, then 0. By the time the calls start finishing, the box holds 0, so all four lines would say *Finishing the call with 0*. The answers would be wrong.

**One bookmark: the call to go back to.** When the call with 1 makes the call with 0, write down "go back to the call with 1". That works once. But the call with 1 had already overwritten the bookmark that said "go back to the call with 2", so after the call with 1 finishes, nobody knows where to go. One bookmark goes back one level; this countdown needs four.

**A list of every call, read from the front.** Keep them all, in the order they started: 3, 2, 1, 0. Going back from the front reaches 3 first, but 3 can't finish yet: it's waiting for 2.

| What we tried | What it keeps | Where it breaks |
|---|---|---|
| One shared `number` | the latest number only | every *Finishing* line says 0 |
| One bookmark | where to go back, one level | it can't go back past the last call |
| Every call, read from the front | all of them, oldest first | it goes back to the oldest call, which is still waiting |

## The questions that lead to it

**What does each waiting call need to keep?** Two things: its own `number`, and the spot in the code to carry on from when the call it made comes back.

**In what order do they come back?** The newest first. The call with 0 finishes, then 1, then 2, then 3: the reverse of the order they started.

You've done this with a recipe book. Step 4 on page 12 says *make the sauce (page 40)*, so you put a bookmark in page 12 and turn to page 40. The sauce says *make the stock first (page 52)*: a second bookmark, in page 40. When the stock is done, you go back to the newest bookmark, page 40; when the sauce is done, page 12. The bookmarks pile up as you go deeper and come out newest first. That's last in, first out: the stack from *Undo the Last Thing First: Stacks*.

## How it got its name

This idea was so useful that it got a name. When a call starts, the computer sets aside a small record for it, called a **stack frame** (or just a frame). The frame holds:

- the call's own parameters and local variables, so `countdown(3)` and `countdown(2)` each have their own `number`;
- the spot in the code to go back to when the call it made finishes, like the bookmark.

The frames live on the **call stack**. When a call starts, its frame goes on top (push); when it finishes, its frame comes off the top (pop), and the program carries on where the frame below it left off.

## Watching the frames

The calls finish in the opposite order to the one they started in. The call with 3 starts first and finishes last, because it can't finish until the call inside it has. Each *Finishing* line prints the right number, because each call reads `number` from its own frame.

![The call stack drawn nine times, left to right, as the countdown runs: the main program's frame alone at the bottom, then frames for 3, 2, 1 and 0 piling on top one at a time, then coming off again newest first until only the main program's frame is left](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/cc444a137f1b4fccacd03a930a2f19bb.webp)

The same story as a table, with the top of the stack on the right:

| Step | What happens | The call stack, bottom to top |
|---|---|---|
| 1 | The program starts | main |
| 2 | `countdown(3)` starts | main, 3 |
| 3 | `countdown(2)` starts | main, 3, 2 |
| 4 | `countdown(1)` starts | main, 3, 2, 1 |
| 5 | `countdown(0)` starts and prints *Liftoff!* | main, 3, 2, 1, 0 |
| 6 | `countdown(0)` finishes | main, 3, 2, 1 |
| 7 | `countdown(1)` finishes | main, 3, 2 |
| 8 | `countdown(2)` finishes | main, 3 |
| 9 | `countdown(3)` finishes | main |

## Answers ride back on the frames

When a call returns a value, the value goes to the frame underneath, which was waiting for it. In `CountDolls` from *How Big Is This Folder? Recursion*, the Green doll's frame is waiting at `1 + CountDolls(...)`. The Blue doll's call returns 1, its frame comes off, and the Green frame carries on: 1 + 1, so it returns 2 to the Yellow frame. That's how the answers come back out, one frame at a time, and why `FolderSize` printed *Beach Trip* before *2024*: the *2024* frame was waiting underneath for its answer.

## Every waiting frame costs memory

At step 5 in the table, five frames are on the stack at once. A countdown from 1,000 would have about a thousand. Recursion that goes n calls deep keeps n frames waiting, so it uses O(n) memory as well as O(n) time. That's the memory half of *Answer It in One Step: Trading Memory for Time*, and it's why a loop that counts down needs only one `number` while the recursive countdown needs one per call.

The call stack is small, a few megabytes at most, so this memory runs out long before your computer's does. That's the stack overflow from *The Folder Tool That Never Stopped: Base Cases*: too many frames waiting at once. The shortcut loop never finished a call, so its frames piled up until there was no room left. Python sets its own limit of about 1,000 frames, and you can see it with `sys.getrecursionlimit()`.

## Seeing it in your debugger

You don't have to imagine the stack: VS Code shows it. Put a breakpoint on the line that prints *Liftoff!* (click left of its line number), then choose **Run > Start Debugging**. When the program pauses, the **Call Stack** section of the Run and Debug view lists one line per frame, newest at the top: four `countdown` calls, above the main program. Click any line, and the **Variables** section shows that frame's own `number`.

![VS Code paused at a breakpoint on the line that prints Liftoff!, with the Call Stack section listing four countdown frames above the main program's, and the Variables section showing number = 0 for the top frame](https://www.ask-codey.com/lessons/TODO)

**Try it.** Change `countdown(3)` to `countdown(5)` and work out, before you run it, how many frames are on the stack when *Liftoff!* prints, counting the main program's. Then check your answer in the debugger.

## Check yourself

2 questions to try on the lesson page.

## So what

The call stack is where every waiting call waits. When you can draw it, you can trace any recursive function by hand, read a stack trace from the newest call down, and explain why recursion that goes too deep runs out of room.

## Key terms

- [Call Stack](https://www.ask-codey.com/glossary/call-stack-data-structures)
- [Stack Frame](https://www.ask-codey.com/glossary/stack-frame)
- [Recursion](https://www.ask-codey.com/glossary/recursion-data-structures)

## Cheat sheets

- [Where Do the Waiting Calls Wait? The Call Stack](https://www.ask-codey.com/cheat-sheets/ds-call-stack-cheat-sheet)

Source: https://www.ask-codey.com/lessons/ds-call-stack
