# Recursion Is Just a Stack You Didn't Write

> Every recursive call is a frame pushed onto the call stack — return address, saved registers, locals. See the frame layout once and stack overflows, tail calls, and the recursion-to-iteration transformation all become mechanical.

URL: https://harshith.in/blog/recursion-and-the-stack/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: fundamentals, systems, algorithms

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.