Recursion: how the call stack actually works

Recursion stops being mysterious the moment you stop watching the code and start watching the stack. The code looks like a function somehow running before it has finished — which is exactly what’s happening, and it works because every unfinished run is parked, in full, on a stack of frames. This page builds that model, because every recursive algorithm on this site (DFS, merge sort, tree traversal, N-Queens) draws its call-frame panel from it, and interviews test the model far more than they test any particular recursive function.

A frame is a bookmark

Calling a function allocates a frame: its parameters, its local variables, and — the crucial part — where in the function it currently is. Call another function (including yourself) and your frame stays put, bookmarked at the call site, while a fresh frame goes on top. Return, and the top frame is torn down; the frame below resumes exactly at its bookmark, locals intact.

That’s the entire trick of recursion: visit(A) calling visit(B) doesn’t overwrite A’s state — B gets its own frame with its own node, its own loop counter, everything. Sixteen nested calls are sixteen bookmarks, each waiting to resume. When people say recursion “magically remembers where it was”, the magic is a stack of structs.

Watch it live: open the DFS visualization and step through — the call-frame panel is the stack, and at every pause it spells out the path from the start node to wherever the search currently stands. The frames aren’t a metaphor for the path; they are the path.

Every call has two moments

The most practically useful fact about recursion: code before the recursive call runs on the way down; code after it runs on the way back up — after everything deeper has fully finished. That one distinction organizes the whole traversal family: emit-then-recurse is pre-order (top-down, “copy this tree”); recurse-then-emit is post-order (bottom-up, “delete this tree”, “compute sizes from leaves”); recurse-left, emit, recurse-right is in-order (sorted output from a BST). Same skeleton, different bookmark placement.

It also explains the pattern behind bottom-up answers: “height of a tree = 1 + max of children’s heights” must be after-the-call code, because the children’s answers don’t exist until their frames have completed. If you’re ever unsure where a line belongs, ask: does it need the deeper results? After. Does it prepare or decide for them? Before.

Writing one without getting lost

Two rules produce correct recursion almost mechanically. Base case first: the input so small the answer is immediate — empty tree, single element, target index reached. Write it before anything else, because every recursive chain must bottom out there. Then trust the call: assume the recursive call works for its smaller input — because by induction, it does — and write your case using its answer. Merge sort’s body is exactly this faith: “both halves come back sorted” is assumed, not verified, and the merge only has to combine two sorted lists. Tracing sixteen frames in your head to convince yourself is the thing to stop doing; the induction does it for you, forever.

The discipline that guards the faith: every recursive call must make progress toward a base case — a smaller range, a shorter list, one more cell fixed. A call that can recurse on the same-sized problem is an infinite descent with a crash at the end.

When the stack becomes the problem

Frames cost memory, and the stack is small — a few megabytes, roughly 10⁴–10⁵ frames depending on the runtime. Recursion depth is a space cost (O(depth)) and a crash risk: DFS on a path-shaped graph of 100,000 nodes, or a naive recursion over a long list, dies with a stack overflow regardless of how correct it is. Python’s default limit is about 1,000 — it will refuse before the OS does.

The conversions, in order of preference: balanced structure (an AVL tree’s recursion is safe because the tree is shallow — sometimes fixing the data beats fixing the code); explicit stack (push what you’d have called, loop while non-empty — mechanical for DFS-shaped code, mildly fiddly for in-order, where you must hand-maintain the “left spine pending” discipline); iteration outright where the recursion was linear anyway (a factorial or list-walk recursion is a for-loop wearing robes). Tail-call optimization — the compiler reusing the frame when the recursive call is the last act — is real in some languages and absent where interviews live (Python never; JavaScript specified but effectively unimplemented), so “it’s tail recursive” is not, in practice, a safety argument there.

What interviewers actually probe

Rarely “write recursion” alone; usually the model behind it. “What’s the space complexity?” — O(depth), and saying it unprompted is the tell you have the frame model. “What does the stack look like right now?” mid-trace — answerable instantly from the bookmark model. “Convert it to iterative” — the explicit-stack drill above. And the backtracking special: state you mutate on the way down must be un-mutated on the way up, in the after-the-call slot, or sibling branches inherit your leftovers — N-Queens’ entire bug surface in one sentence, and the reason its visualization counts backtracks as a first-class event.