Recursion

Status: 🟩 COMPLETE Last updated: 2026-06-19 Plain-English tagline: A function that calls itself, breaking a big problem into smaller copies of the same problem. Natural for tree-shaped data; powerful when used right; the cause of “stack overflow” when used wrong.

In plain English

A recursive function is a function that calls ITSELF. It looks weird the first time you see it — “isn’t that infinite?” — but it isn’t, as long as each call moves toward a “base case” that doesn’t recurse.

The classic example: factorial.

function factorial(n) {
  if (n <= 1) return 1;          // base case
  return n * factorial(n - 1);   // recursive case
}
 
factorial(5);
// = 5 * factorial(4)
// = 5 * 4 * factorial(3)
// = 5 * 4 * 3 * factorial(2)
// = 5 * 4 * 3 * 2 * factorial(1)
// = 5 * 4 * 3 * 2 * 1
// = 120

Each call to factorial solves a slightly smaller version of the problem. Eventually n hits 1, the base case returns directly, and the stack unwinds.

The technique is most natural for problems with RECURSIVE STRUCTURE — data that contains smaller copies of itself:

Trees — a tree node has children, which are themselves trees
Nested data — JSON with nested objects, arrays of arrays
The filesystem — folders contain folders
The DOM — elements contain elements
Math — factorial, Fibonacci, GCD, binomial coefficients

For data that’s flat (a list of numbers), recursion is usually overkill — a loop is clearer. For data that’s nested, recursion often matches the shape.

This entry covers when to USE recursion, when to AVOID it, and the common patterns. For algorithmic analysis of recursive code, see Time & space complexity (Big-O).

Why it matters

Three reasons recursion is worth understanding:

It’s everywhere in modern code. Tree walks, JSON processing, AI agents recursively calling themselves, recursive React component trees — all natural matches.
It can be elegant or disastrous. Same problem, recursive solution is sometimes 5 lines vs 50 iterative. But naive recursion can crash with stack overflow on big input.
AI tools use recursion frequently in generated code. Understanding what’s happening is essential to reviewing it.

The trade-off: recursion has performance + memory cost (each call uses stack memory). For very deep recursion, iteration (loops) is safer. Choosing between is a judgment call.

The two ingredients of every recursive function

Base case — the condition under which the function does NOT recurse. Without this, infinite recursion → stack overflow.
Recursive case — the function calls itself with a SMALLER / SIMPLER input. Each call moves closer to the base case.

Together they form an inductive structure: “If I can solve the base case, and I can solve the problem of size n given the solution to size n-1, I can solve any size.”

Examples of base cases:

if (n === 0) return 1 (math)
if (node === null) return (tree traversal)
if (array.length === 0) return [] (list processing)
if (depth > maxDepth) return (depth-limited search)

If you write a recursive function and forget the base case, the first thing that happens is stack overflow.

A concrete example: walking a tree

Say you have a nested JSON object representing a file tree:

const tree = {
  name: "src",
  children: [
    { name: "components", children: [
      { name: "Button.tsx", children: [] },
      { name: "Card.tsx", children: [] },
    ]},
    { name: "lib", children: [
      { name: "utils.ts", children: [] },
    ]},
  ],
};

Count all files (leaves) iteratively — annoying:

function countFiles(tree) {
  let count = 0;
  const stack = [tree];
  while (stack.length > 0) {
    const node = stack.pop();
    if (node.children.length === 0) count++;
    else stack.push(...node.children);
  }
  return count;
}

Recursively — natural:

function countFiles(node) {
  if (node.children.length === 0) return 1;        // base case
  return node.children.reduce(
    (sum, child) => sum + countFiles(child),         // recurse
    0
  );
}

The recursive version says: “the file count of this subtree is 1 (if it’s a leaf) or the sum of file counts of its children.” That’s natural; matches the structure.

When data is tree-shaped, recursion is usually the clearer approach.

Iterative vs recursive — when to use which

The same problem can often be solved either way. Decision factors:

Use recursion when	Use iteration when
Data is naturally tree-shaped	Data is flat
Problem has natural sub-problems (divide and conquer)	You’re just walking through items
Code is much clearer recursively	Recursive version is convoluted
Depth is bounded (won’t exceed ~1000)	Depth could be huge or unbounded
Performance isn’t tight	Hot path, every microsecond matters

For JavaScript specifically, the stack depth limit is around 10,000 (varies by engine). Recursion deeper than that crashes with “Maximum call stack size exceeded.”

For 99% of webapp work, recursion is safe and natural where it fits. The 1% where it isn’t: processing massive trees, parsing huge expressions, etc.

The famous recursive patterns

1. Tree traversal

Visit every node in a tree. Two main orders:

Depth-first (recursive, most natural):

function dfs(node) {
  console.log(node.value);     // process THIS node
  for (const child of node.children) {
    dfs(child);                 // then recurse into each child
  }
}

Variants: pre-order (process before recursing), in-order (for binary trees), post-order (process after recursing).

Breadth-first (uses a queue; usually iterative):

function bfs(root) {
  const queue = [root];
  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node.value);
    queue.push(...node.children);
  }
}

BFS visits all nodes at the same depth before going deeper. Used for “shortest path” problems.

2. Divide and conquer

Split the problem in half, solve each half, combine. Classic for sorting:

function mergeSort(arr) {
  if (arr.length <= 1) return arr;       // base case
 
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));    // recurse
  const right = mergeSort(arr.slice(mid));      // recurse
 
  return merge(left, right);              // combine
}
 
function merge(a, b) {
  const result = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) result.push(a[i++]);
    else result.push(b[j++]);
  }
  return [...result, ...a.slice(i), ...b.slice(j)];
}

Each recursion halves the input. The depth is O(log n); work at each level is O(n). Total: O(n log n).

3. Backtracking — trying all options

For problems where you explore choices and undo when they don’t work.

function permutations(arr) {
  if (arr.length === 0) return [[]];
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
    for (const p of permutations(rest)) {
      result.push([arr[i], ...p]);
    }
  }
  return result;
}
 
permutations([1, 2, 3]);
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Used in sudoku solvers, n-queens, constraint satisfaction, AI search.

4. Memoized recursion (dynamic programming)

When subproblems repeat, cache results:

const memo = new Map();
function fib(n) {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fib(n - 1) + fib(n - 2);
  memo.set(n, result);
  return result;
}

Without memoization: O(2ⁿ) — exponential, gets slow at n=40. With memoization: O(n) — linear, fast at n=1,000,000.

This is the bridge between recursion and dynamic programming.

The call stack — what happens during recursion

When a function calls another, the runtime PUSHES a “stack frame” — info about local variables, return address, etc. — onto a stack. When the function returns, the frame is POPPED.

Recursion makes the stack grow. Calling factorial(5):

Call factorial(5):
  Stack: [factorial(5)]
  → calls factorial(4):
    Stack: [factorial(5), factorial(4)]
    → calls factorial(3):
      Stack: [factorial(5), factorial(4), factorial(3)]
      → calls factorial(2):
        Stack: [factorial(5), factorial(4), factorial(3), factorial(2)]
        → calls factorial(1):
          Stack: [factorial(5), factorial(4), factorial(3), factorial(2), factorial(1)]
          → returns 1
        ← receives 1, returns 2*1 = 2
      ← receives 2, returns 3*2 = 6
    ← receives 6, returns 4*6 = 24
  ← receives 24, returns 5*24 = 120
Final: 120

The stack grows then shrinks. Each frame has its own copy of local variables (n).

The DANGER: each frame uses memory. JavaScript’s stack limit is ~10,000 frames. A recursion 100,000 deep crashes.

Tail recursion (and why JavaScript doesn’t help)

A tail call is a recursive call that’s the LAST thing the function does. In languages with tail-call optimization (TCO), the compiler can reuse the current stack frame instead of pushing a new one → recursion uses O(1) stack space.

Tail-recursive factorial:

function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc);   // last action is the recursive call
}

In Scala, Scheme, Haskell, Erlang — this would run with no stack growth.

In JavaScript: the spec includes TCO. The reality: V8 (Chrome / Node), SpiderMonkey (Firefox), and Safari all DON’T implement it. (Long story; security concerns about stack traces.)

So in JavaScript, even tail-recursive functions blow the stack on deep input. Convert to iteration for deep recursion.

When recursion is wrong

Sometimes the recursive solution is wrong. Sometimes worse than wrong — accidentally exponential.

Naive Fibonacci

function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

This LOOKS right. But each call branches into TWO. fib(40) makes over a billion calls. Without memoization, it’s exponential.

”Find all permutations” with deep input

function permutations(arr) { /* as above */ }

For an array of 10 items: 3.6M permutations. For 20 items: 2.4 quintillion. Recursive code that “works” for small input can be catastrophic for medium input.

When recursion produces exponential time or space, refactor:

Memoize if subproblems repeat (turns exponential into polynomial)
Iterate if recursion is just walking through (use a stack/queue explicitly)
Question whether you need the full result (maybe yield lazily with a generator)

Common gotchas

Missing base case = stack overflow. First thing to check when recursion crashes.
Recursion in JavaScript blows the stack at ~10,000 deep. Less in some environments. For deeper data, convert to iteration with an explicit stack.
Tail recursion doesn’t help in JavaScript. The spec allows TCO; no major engine implements it.
Each call creates closures and uses memory. A million recursive calls = a million stack frames = significant memory.
Mutating shared state in recursion can cause subtle bugs. A function that adds to a shared array can interleave weirdly. Prefer pure functions.
for...in and for...of on recursive data is tricky. Iterating siblings while recursing into children — easy to confuse.
JSON.parse is recursive internally. Deeply nested JSON can blow the stack. For very deep JSON, use a streaming parser.
React.createElement produces a recursive tree. When you write JSX, you’re describing a recursive structure. React’s reconciler walks it recursively.
Calling a recursive function in a loop multiplies cost. Profile before relying on it for hot paths.
Recursive type definitions in TypeScript can confuse the compiler. Deeply recursive types may hit the type-checker’s recursion limit (different from runtime). Sometimes you need explicit unions.
Walking a graph with cycles via recursion = infinite loop. Trees have no cycles by definition; graphs can. Track visited nodes (Set) to detect cycles.
The “rabbit” hole metaphor. A recursive function “going down the rabbit hole” comes back UP through the stack. Each return resumes the call that initiated it. Print statements before AND after the recursive call show this.
In React, recursion appears in components. A <MenuItem> containing <MenuItem>s. React handles the recursion via its reconciler; you write it naturally as JSX.
Indirect recursion is harder to spot. A calls B, B calls A. Same risks; harder to find in code review.
Tree mutation during recursion is hazardous. Modifying a tree while walking it can produce surprising results. Walk first, mutate after, or use explicit traversal.
The depth of a tree determines stack usage, not the SIZE. A balanced tree of 1M nodes has depth ~20. A linked-list-shaped tree (every node has one child) of 1M nodes has depth 1M — instant stack overflow.
for await...of is iteration, not recursion. Async iteration is its own thing.
AI tools often write naive recursion when memoization or iteration is needed. Watch for “recursive Fibonacci”-style patterns; they look elegant but blow up.
For traversal, prefer explicit recursion over generic “map” tricks. A flatMap over a deeply nested array doesn’t actually walk arbitrary depth; it flattens one level.
structuredClone handles cyclic objects. Manual deep clone via recursion does NOT — you’ll infinite-loop on obj.self = obj. Either detect cycles or use structuredClone.
Recursion in Web Workers gets its OWN stack. Same JavaScript engine limit, but workers run independently. Doesn’t really help avoid stack overflow.
Recursion is rarely the BOTTLENECK in webapp work. Network, database, rendering dominate. Worry about recursion’s performance only if profiling identifies it.
Tree operations are usually safe at webapp scales. Component trees (~hundreds of nodes), JSON config files, file trees (~thousands) — well under the stack limit.
Big-O of recursion can be tricky to compute. Each call costs O(1) of stack frame + whatever work it does. Total = work-per-call × number-of-calls. For divide-and-conquer, use the Master Theorem (or just memorize: merge sort is O(n log n)).
Don’t write recursion just because it’s “elegant.” If the iterative version is clearer to the next reader, use that. Clarity > cleverness.

When to reach for recursion

Use recursion when:

The data has tree / nested structure
The problem naturally splits into smaller copies of itself
You’re processing JSON / DOM / file trees / abstract syntax trees
The iterative version requires manually managing a stack anyway
Depth is bounded and reasonable (< ~1000)

Avoid recursion when:

Data is flat (just use a loop)
Depth could be huge (use iteration with explicit stack)
The problem is iterative (counting, summing, filtering)
You’re rewriting basic operations recursively for “elegance” (it’s not — clarity is)
Performance is critical and you’re not sure about constants

For Bible Quest-style projects, recursion shows up most in: JSON processing, React component trees (handled by React itself), and the occasional menu/sidebar tree component.

Sources

MDN — Recursion
Eloquent JavaScript — Chapter on Functions — covers recursion clearly
Structure and Interpretation of Computer Programs — the classic deep dive (free PDF)
The Little Schemer — recursion-first introduction to programming

Tech & AI, Explained

Explorer

recursion