Tags: web-dev concept

Recursion

Date: 2026-08-17

---

A function that calls itself on a smaller version of the problem. It’s the natural fit for anything tree-shaped — and the honest choice far less often than people who have just understood it believe.

---

Recursion solves a problem by reducing it to a smaller instance of the same problem, until a case small enough to answer directly is reached.

Two parts, and omitting either is the whole failure mode:

BASE CASE       when to stop
RECURSIVE CASE  the smaller problem

The mechanism

Every call gets a stack frame — its own parameters and local variables, pushed onto the call stack. The frames unwind in reverse when the base case returns.

sumTo(3)
  ├ frame: n=3, waiting on sumTo(2)
  │   ├ frame: n=2, waiting on sumTo(1)
  │   │   └ frame: n=1 → returns 1   ← base
  │   └ returns 2 + 1 = 3
  └ returns 3 + 3 = 6

three frames alive at once

That’s the cost. Depth n means n frames in memory simultaneously, and the stack is a fixed, fairly small budget — Memory Models.

RangeError: Maximum call stack size exceeded

Usually means a missing base case, an infinite structure, or genuinely deep data.

Where it’s clearly right

Tree-shaped data, where the structure is recursive so the code matching it is too:

function findNode(node, id) {
  if (node.id === id) return node        // base
  for (const child of node.children) {
    const hit = findNode(child, id)      // recurse
    if (hit) return hit
  }
  return null                            // base
}

The iterative version needs an explicit stack and is longer and harder to read for no benefit. Real cases: DOM traversal, JSON walking, file trees, comment threads, nested categories, parsers.

Where iteration is the honest choice

RECURSIVE                ITERATIVE
sumTo(n)                 for (i = 1; i <= n; i++)
  n stack frames           one variable
  stack overflow at        works to any n
  ~10,000

A linear sequence is a loop. Writing it recursively is a demonstration, not a solution — and the vault’s test applies: does this exist to help you understand, or to show that you do?

The trap: exponential recursion

The classic, and it’s a real bug pattern rather than a textbook curiosity:

fib(5)
├ fib(4)
│ ├ fib(3)
│ │ ├ fib(2) ...
│ │ └ fib(1)
│ └ fib(2)   ← computed again
└ fib(3)     ← computed AGAIN

fib(40) ≈ 331 million calls

Each branch recomputes work its sibling already did — O(2ⁿ) — Time and Space Complexity.

The fix is memoisation: cache each result by input, so each distinct call happens once. O(2ⁿ) becomes O(n). This is the general shape of dynamic programming, and it’s the same idea as a cache — Caching Strategies.

Tail calls, and why they don’t help you

A tail call is a recursive call that is the last thing a function does, so its frame could be reused rather than stacked. Languages implementing tail-call optimisation turn such recursion into a loop with constant stack use.

JavaScript specified it and mostly didn’t implement it. Safari’s JavaScriptCore does; V8 (Chrome, Node) and SpiderMonkey (Firefox) do not. So writing tail-recursive JavaScript buys nothing portable — assume every recursive call costs a frame.

Practical rules

• Write the base case first. Most infinite recursion is a base case that doesn’t catch every terminating condition
• Guard against cycles. A graph with a loop recurses forever. Keep a Set of visited nodes — this is why a naive deep-clone breaks on circular references
• Bound the depth on anything derived from user input or external data. Untrusted deeply-nested JSON is a denial-of-service vector
• Convert to iteration when depth is unbounded, using an explicit stack array. Uglier, and it fails gracefully rather than crashing