All topics
26 / 100
Functionsintermediate

Recursion and Stack Depth

Writing functions that call themselves to solve problems by breaking them into smaller subproblems, and the call-stack limits that come with it.

A recursive function calls itself, and each call adds a frame to the stack. That limit is the practical constraint.

Recursion is like a set of Russian nesting dolls: each doll (call) contains a smaller version of the same problem, and you only start putting them back together (returning) once you hit the smallest, solid doll (the base case) that can't be opened further.

Key Concepts

1
    function factorial(n) {
      if (n <= 1) return 1;        // base case
      return n * factorial(n - 1); // recursive case
    }
2
A base case is not optional. Without one, or with one that is never reached, the stack fills:
3
    RangeError: Maximum call stack size exceeded
4
The limit is around 10,000 frames in most browsers, and it depends on how much each frame holds.
5
Where recursion is genuinely the right tool: nested structures.
    function flatten(arr) {
      return arr.reduce((out, x) =>
        out.concat(Array.isArray(x) ? flatten(x) : x), []);
    }
6
    function deepClone(o) {
      if (o === null || typeof o !== 'object') return o;
      return Array.isArray(o)
        ? o.map(deepClone)
        : Object.fromEntries(
            Object.entries(o).map(([k, v]) => [k, deepClone(v)]));
    }
7
Trees, nested JSON, directory structures and the DOM are all recursive shapes, and iterating them without recursion means managing your own stack.
8
Which is also the fix when depth is a problem.
    // recursive -- fails on a deep tree
    function walk(node) {
      visit(node);
      node.children.forEach(walk);
    }
9
    // iterative -- bounded by memory, not the call stack
    function walk(root) {
      const stack = [root];
      while (stack.length) {
        const node = stack.pop();
        visit(node);
        stack.push(...node.children);
      }
    }
10
Same traversal. The explicit stack lives on the heap, so a tree 100,000 deep is fine.
11
Tail call optimisation does not save you. The specification includes it; Safari implements it and the other engines do not. Writing a function in tail position and relying on the optimisation is not portable.
12
Memoisation is the other common pairing.
    const memo = new Map();
    function fib(n) {
      if (n <= 1) return n;
      if (memo.has(n)) return memo.get(n);
      const v = fib(n - 1) + fib(n - 2);
      memo.set(n, v);
      return v;
    }
13
Naive fib(40) makes over a billion calls; memoised, it makes forty. The recursion was not the problem — recomputing the same subproblems was.
fib(40)
14
The judgement. Recursion for nested data of bounded depth, where it reads clearly. Iteration when the depth is unbounded or driven by input you do not control.
15
What the interviewer is probing.1. "What limits recursion depth in JavaScript?" Probing: the engine. Stalls: "Memory." Moves up: the call stack — exceeding it throws RangeError with maximum call stack size exceeded, typically around ten thousand frames.
16
2. "Does JavaScript have tail call optimisation?" Probing: the honest state. Stalls: "Yes, in ES6." Moves up: it is specified but only Safari implemented it, so deep recursion cannot rely on it.
17
3. "How do you convert deep recursion to iteration?" Probing: the technique. Stalls: "You cannot." Moves up: keep an explicit stack array and loop, which moves the frames to the heap.
18
4. "When is recursion the right choice?" Probing: judgement. Stalls: "When it is shorter." Moves up: for naturally recursive structures like trees where depth is bounded by log n; iteration for anything that can go deep.
Use cases:algorithmsrecursionadvanced