Function calls and the call stack.
Every function call grows the stack by one frame. Every return shrinks it by one. The CPU keeps track of where to jump back to with a saved return address. Recursion isn't magic — it's the same mechanism applied to itself. Watch factorial(3) execute step by step: three pushes growing the stack, then three pops unwinding it as the return values bubble up.
factorial(3) = 3 × 2 × 1 = 6 Recursive · base case at n=1 · max stack depth 4 (main + 3 × factorial)Program loads. The CPU is about to execute the very first instruction — the call to main() on line 12. The stack is empty. The OS will give control back to the loader once main() returns.
- Call stack
- A region of memory the CPU uses to track who called whom. Each function call pushes a frame, each return pops one.
- Stack frame
- One function's private workspace on the stack: its arguments, its locals, and the return address back to its caller.
- Program counter (PC)
- The CPU register holding the address of the next instruction to execute. A function call sets it to the callee, a return sets it back.
Why recursion is just calling, repeated
There's nothing special about a function calling itself. The CPU doesn't know or care that the caller and callee share a name — it pushes a new frame, sets up a new return address, sets the PC to the function's entry point, and starts executing. Each frame has its own arguments, its own locals. They don't collide because they live at different addresses.
The mental model people get stuck on is the unwinding. It feels like the work happens on the way down, but for factorial(n) the actual multiplications happen on the way back up — each frame multiplies its n by what the callee returned. Watch the RAX register: it carries 1, then 2, then 6, accumulating as frames pop.
Iteration is the same machine, different choreography
Rewrite factorial as a loop and the stack stays at depth 1 — main + factorial. The loop variable lives in a register or the single frame; no new frames are pushed. Same answer, no risk of overflow. For deep computations (n in the millions) this is the difference between "works" and "stack overflow at frame 261,000."
Tail-call optimisation, when a compiler does it, lets a recursive function reuse the caller's frame if the call is in tail position — turning the recursion into a loop in disguise. Scheme requires it, OCaml does it, Java doesn't, V8 does sometimes. Worth checking before assuming.
What this visualization simplifies
- Register-passed arguments. On x86-64 / ARM64, the first 6 args go in registers, not on the stack. The frame doesn't grow for them. We drew them in the frame for clarity.
- Inlining. An optimising compiler often eliminates the call entirely by pasting the callee\'s body into the caller. Then there\'s no frame at all.
- Red zone. Below SP, the System V ABI reserves 128 bytes a leaf function can use without adjusting SP. We ignored this.
- Stack canaries. Real compiled code inserts a guard value between locals and the saved return address. If buffer-overflow code stomps the canary, the program aborts before returning into hijacked memory.
- Exceptions. When an exception is thrown, the runtime unwinds frame by frame, running destructors / finally blocks along the way, until it finds a catch. Same stack, different exit path.
How stack overflow actually happens
Each thread has a fixed stack — usually 1 MB on Windows, 8 MB on Linux, configurable per-thread when you spawn one. A typical frame is ~64 bytes (args + return addr + saved FP + a few locals). Divide and you get roughly 15,000–130,000 frames before you run out. Recurse a tree of depth 10,000 and you're fine. Recurse linearly down a million-element linked list and you crash.
The cure for the linked-list case is iteration. The cure for deep but not-pathological recursion (parsers, tree walkers) is to either grow the stack at thread creation, or to convert recursion to iteration using an explicit work-queue or stack data structure on the heap — where there's gigabytes available.
Recursion patterns in the Problem-Solving Codex →
When to recurse, when to iterate, when to memoise, when to use an explicit stack. Pattern recognition for the algorithms that matter in interviews.
Open the Codex