---
title: "Recursion & the Call Stack"
description: "Calls pushed and popped, return values, and a recursion unwinding frame by frame."
source: https://vizlearn.app/foundations/abstraction/recursion-call-stack
---

# Recursion & the Call Stack

Recursion and the call stack describe how a function calls itself without losing its place. Each call creates a stack frame, the newest frame runs first, and a return value travels back to the caller waiting below it. That stored frame is also why deep recursion can crash before the math gets hard.

The physical model is a stack of sticky notes. You write `fact(4)` on the first note, then it says, "I need `fact(3)` before I can finish." So you put a new note on top. Only the top note gets your attention. The lower notes are not gone; they are just waiting with unfinished work. In the animation, each sticky note is one stack frame, and a "note waits" label means that frame has unfinished local work.

## Why recursion needs the call stack

A recursive function has two jobs. First, it needs a **base case**: a condition that can return without making another recursive call. Second, it needs a **recursive case**: a call on a smaller input, followed by whatever work uses that returned answer.

For factorial, the base case is `n <= 1`, which returns `1`. The recursive case for `fact(n)` asks for `fact(n - 1)`, stores that answer as `child`, then returns `n * child`.

That word "stores" matters. When `fact(4)` calls `fact(3)`, the `fact(4)` frame does not vanish. It stays on the call stack with its local `n = 4` and an unfinished slot, `child = ?`. When `fact(3)` eventually returns `6`, that value lands in the waiting slot, and only then can `fact(4)` compute `4 * 6`.

This is last-in, first-out control flow. The last call pushed is the first one that can return. The practical lesson is already visible here: every waiting frame costs stack memory.

## Recursion & the Call Stack Step by Step

The default run computes `fact(4)`.

1. The program starts at `answer = fact(n)`, with `n = 4`. The stack is empty.
2. `fact(4)` is called, so a new frame is pushed. That frame has local state `n = 4`.
3. The frame checks `4 <= 1`. The answer is false, so it cannot return yet.
4. `fact(4)` pauses at `child = fact(3)`. Its `child` slot is waiting.
5. `fact(3)` is pushed on top. Now `fact(3)` runs, while `fact(4)` waits below it.
6. `fact(3)` checks `3 <= 1`, gets false, and pauses at `child = fact(2)`.
7. `fact(2)` is pushed, checks `2 <= 1`, gets false, and pauses at `child = fact(1)`.
8. `fact(1)` is pushed. Its guard `1 <= 1` is true, so the base case returns `1`.
9. That `1` is delivered to the caller, `fact(2)`, filling `child = 1`.
10. `fact(2)` can now finish: it returns `2 * 1 = 2`.
11. That `2` lands in `fact(3)` as `child = 2`, so `fact(3)` returns `3 * 2 = 6`.
12. That `6` lands in `fact(4)` as `child = 6`, so `fact(4)` returns `4 * 6 = 24`.
13. The root return value becomes `answer = 24`, and the stack is empty again.

The important visual signal is the direction change. Calls push frames upward; returns move values downward into the caller that was waiting. If you can explain why `fact(2)` finishes before `fact(4)`, you have the call-stack model.

After the normal run, switch the code variant to `missingBase`. Remove the base case and watch why recursion must stop: every top frame asks for one more frame, and none of them reach a return.

## Time and Space Complexity

| Variant | Time complexity | Stack space | What happens |
|---|---:|---:|---|
| `fact(n)` with a base case | O(n) | O(n) | For `n >= 1`, one frame per value from `n` down to `1`, then one return per frame. |
| `fact_without_base(n)` | Does not terminate | Grows until a recursion limit | Every frame calls another frame; no frame reaches a return. |

Under this lesson's unit-cost model, the normal factorial program does constant work in each frame: one guard, maybe one recursive call, and at most one multiplication on the way back. With `n` frames, that is O(n) time and O(n) stack space. That stack-space line is the practical bite: if `n` can be huge, deep recursion can crash before the math is hard, which is when you rewrite it as a loop, use an explicit stack, or change the recursion limit only on purpose.

The missing-base variant is not "slow factorial." It is not factorial at all. It has no stopping rule, so the only thing that halts it is the runtime's recursion limit. Python's default limit is around 1000 frames, not six; this lesson uses a tiny visible cap so you can see the failure before the screen turns into wallpaper.

## Edge Cases

- `n = 1` hits the base case immediately. One frame is pushed, returns `1`, and pops.
- The maximum normal input here is `n = 6`, not because factorial stops there, but because six frames are the largest stack that fits cleanly on the teaching canvas.
- In the missing-base variant, negative values do not save you. `fact_without_base(-2)` still calls `fact_without_base(-3)`, then `-4`, then keeps going.
- A return value always goes to exactly one place: the caller's waiting `child` slot, or the global `answer` slot for the root call.

## Common Mistakes

- Thinking recursion creates copies of the whole program. It creates a new **frame** for the same function, with its own local variables.
- Forgetting that callers are suspended. `fact(4)` cannot multiply until `fact(3)` has returned.
- Treating the base case as optional. Without it, the stack grows until the runtime stops the program.
- Mixing up return order with call order. Calls go `4, 3, 2, 1`; returns come back `1, 2, 6, 24`.
- Reusing one shared `child` variable in your mental model. Each frame has its own `child`; `fact(2).child` and `fact(4).child` are different slots.

## A Note on Simplification

This visualization shows a teaching stack frame: function name, argument, local `child`, and return value. Real Python frames also carry bytecode positions, globals, closure references, exception state, and interpreter bookkeeping. Those details matter to runtime engineers, but they would hide the first idea: recursion works because each call has its own frame, and the top frame is the only one currently running.