Recursion gets taught as a leap of faith: “assume the function works for n-1.” Fine for proofs, useless for debugging. The demystifying move is to look at what the machine does — because the machine doesn’t do faith, it does a stack of frames, and every property of recursion (why it overflows, why it can be slow, why some recursion is free) is a property of that stack.

What a Call Actually Costs

When factorial(5) calls factorial(4), the CPU pushes a return address and jumps; the callee’s prologue then reserves space for its frame:

text
   high addresses
   ┌──────────────────┐
   │ factorial(5)      │  n=5, return addr into caller
   ├──────────────────┤
   │ factorial(4)      │  n=4, return addr into factorial(5)
   ├──────────────────┤
   │ factorial(3)      │  n=3, ...          ◀── rsp
   └──────────────────┘
   grows downward

Each frame holds the return address, saved registers, and locals — typically a few dozen bytes, more if you have big local arrays. The frames are why recursion “remembers where it was”: the pending multiplications of n * factorial(n-1) live in those suspended frames, waiting for the recursion to bottom out and unwind.

Two costs follow. Per call: push, jump, prologue, epilogue — a handful of cycles, which only matters when the work per call is tiny (a fibonacci that does one addition per call is mostly paying call overhead). And cumulatively: the stack is finite — 8 MB default on Linux (ulimit -s), a fixed guard-page-protected mapping. Recurse 100,000 deep with 100-byte frames and you hit the guard page: SIGSEGV, the famous stack overflow. Depth proportional to input size is a latent crash: a recursive-descent parser fed deeply nested JSON, a naive quicksort fed sorted input, a linked-list destructor freeing ten million nodes recursively — all real-world overflow reports.

Tail Calls: Recursion Without the Stack

If the recursive call is the very last thing the function does — nothing pending after it returns — the current frame is dead weight. A tail call can reuse it: replace call-and-return with a jump. Depth becomes O(1); the recursion is now, mechanically, a loop.

c
/* NOT a tail call: the multiply happens after the call returns */
return n * factorial(n - 1);

/* tail call: accumulator carries the pending work */
return factorial_acc(n - 1, n * acc);

GCC and Clang perform this at -O2 (watch the assembly turn into a plain loop), but C doesn’t guarantee it — so you can’t rely on it for correctness, only speed. Scheme guarantees it; so does Lua; Python famously refuses on the grounds that it destroys tracebacks. If your language doesn’t promise TCO, unbounded-depth recursion is a bug regardless of how elegant it looks.

The Mechanical Transformation

Since recursion is a stack, any recursion can become iteration with an explicit stack — heap-allocated, so it’s bounded by memory instead of 8 MB:

c
void traverse(Node *root) {
    Stack s = {0};
    push(&s, root);
    while (!empty(&s)) {
        Node *n = pop(&s);
        if (!n) continue;
        visit(n);
        push(&s, n->right);   /* push right first: left is processed first */
        push(&s, n->left);
    }
}

You’re storing exactly what the call stack stored — pending work — minus the return addresses and register spills, which is why the explicit version often uses less memory per level. For tree/graph traversal this transformation is routine; for something like quicksort, hybrid is idiomatic: recurse on the smaller partition, loop on the larger — depth bounded at O(log n) even in the pathological case.

When to leave recursion alone: when depth is provably shallow (balanced trees: depth 60 covers 10¹⁸ nodes) and the recursive version is clearer. Clarity is worth a lot; an 8 MB stack is deeper than people fear for balanced structures. The danger is exclusively input-proportional depth on inputs you don’t control.

Takeaways

  • A recursive call is a frame push: return address + saved state. Pending work lives in suspended frames.
  • Stack space is fixed (~8 MB); input-proportional recursion depth is a crash waiting for the right input.
  • Tail calls can compile to jumps (O(1) depth) — guaranteed in Scheme/Lua, best-effort in C, absent in Python.
  • Any recursion converts to iteration with an explicit heap stack; recurse-small/ loop-large bounds quicksort at O(log n) depth.
  • Keep recursion where depth is logarithmic and clarity wins; replace it where the input controls the depth.