Beyond recursion

Recursion is a lovely way to describe a problem. You call the function again, the stack remembers the unfinished work, and everything feels inevitable — right up until the tree turns out to be a graph, one path runs 80,000 nodes deep, and the user clicks cancel while your elegant definition has nowhere to put the request.

The stack made choices#

A recursive traversal makes a pile of decisions without telling you: depth-first order, last-in-first-out scheduling, one active branch at a time, one frame per level. The state didn't go away. It moved into the call stack, which happens to be the one place where you can't easily inspect it, budget it, pause it, or write it to disk.

Python's recursion limit exists to stop that hidden state from blowing through the C stack, which tells you something — the runtime already treats your tidy definition as a hazard to contain.

Compare the pretty version with the honest one:

function walk(node: Node): void {  if (seen.has(node.id)) return;  seen.add(node.id);  consume(node);  for (const child of node.children) walk(child);}

const pending = [root];let budget = 10_000;while (pending.length && !signal.aborted && budget-- > 0) {  const node = pending.pop()!;  if (seen.has(node.id)) continue;  seen.add(node.id);  consume(node);  pending.push(...node.children);}

The second version admits there's pending work, a budget, cancellation, and a cycle policy. And once the machinery is on the table you can mess with it: swap pop() for a queue and the order changes, swap in a priority queue and you get to decide what matters first.

Recursive syntax, iterative engine#

Mature systems already make this split. PostgreSQL's recursive query documentation is upfront about it: the syntax is recursive, but the engine evaluates it iteratively with a working table. Clang's data-flow analysis guide does the same dance, putting changed blocks back onto a worklist queue until the analysis reaches a fixpoint.

That's the whole move: separate what repeats from how unfinished work gets scheduled. Folds and iterators do it for sequences, worklists for graphs, streams for values arriving over time, fixed-point engines for facts that keep producing more facts.

Keep recursion where it tells the truth#

Use recursion when the input is bounded and tree-shaped and the call stack happens to be the schedule you want — a small syntax tree transform, say. I still reach for it there without a second thought. But once you need pause and resume, deduplication, parallelism, checkpoints, or any kind of progress reporting, those six lines aren't elegant anymore; they're hiding the hard part.

None of this bans self-reference. Keep the recursive definition — it's usually the clearest statement of the problem — and promote the progress to data, so unfinished work can be inspected, reordered, cancelled, or picked back up after a crash. The program reads about the same, and now you can actually operate it.