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
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.
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);
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
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);
}
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
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)
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
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);
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
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);
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)andcountdown(2)each have their ownnumber; - 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 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.
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.