JavaScriptRecursion

Recursion

A recursive function is one that calls itself to solve a smaller version of the same problem. Recursion is not just a clever trick; it is the natural fit for problems with self-similar structure — trees, nested data, parsing, divide-and-conquer algorithms. The key is two ingredients: a base case that stops the recursion, and a recursive case that moves toward it.

The two ingredients

  • Base case — the smallest input the function can answer directly, without calling itself again.

  • Recursive case — the function reduces the problem and calls itself on the smaller version.

Forget the base case and you get infinite recursion. Forget to reduce the problem and you also get infinite recursion. Always answer both questions when writing one.

The canonical example — factorial

JS
function factorial(n) {
  if (n <= 1) return 1;          // base case
  return n * factorial(n - 1);   // recursive case
}

console.log(factorial(5));   // 120  (5 * 4 * 3 * 2 * 1)
console.log(factorial(0));   // 1

At each step, the function builds up: 5 * factorial(4) → 5 * 4 * factorial(3) → ... → 5 * 4 * 3 * 2 * 1 * 1. Five recursive calls are stacked, then they unwind multiplying as they go.

What the call stack actually does

Each recursive call adds a new stack frame holding local variables and the return location. When the base case returns, frames pop off one by one. You can see this in DevTools by setting a breakpoint inside the recursive function — the call stack panel shows the whole chain.

JS
function count(n) {
  if (n === 0) return;
  console.log(n);
  count(n - 1);
}

count(3);
3
2
1

Three stack frames build up, then unwind in reverse.

Stack overflow — the limit

The call stack has a fixed size. Recurse too deep and the engine throws RangeError: Maximum call stack size exceeded. In typical browsers and Node, the limit is around 10,000 frames for simple functions.

JS
function deep(n) {
  return deep(n + 1);
}
// deep(0);   // RangeError after ~10000 calls
When recursion meets a million
If your input could be huge (a deeply nested JSON, a long list), prefer an iterative loop or an explicit stack stored on the heap. Recursion is for problems that are *recursively shaped*, not just for replacing loops.
Walking a tree

Trees are recursion's natural home: each node is a "root with subtrees", which is itself a tree.

JS
const tree = {
  name: "root",
  children: [
    { name: "a", children: [] },
    { name: "b", children: [
      { name: "b-1", children: [] },
      { name: "b-2", children: [] },
    ]},
  ],
};

function listNames(node, indent = 0) {
  console.log(" ".repeat(indent) + node.name);
  for (const child of node.children) {
    listNames(child, indent + 2);
  }
}

listNames(tree);
root
  a
  b
    b-1
    b-2
Recursion vs iteration

Anything you can do with recursion you can technically do with a loop, and vice versa. Choose based on which one matches the problem:

  • Recursion is clearer for tree-shaped data, divide-and-conquer (quicksort, merge sort), and parsing.

  • Iteration is clearer for linear problems — summing a list, counting up to N, scanning a string.

  • When in doubt, write whichever is easier to read. Premature optimisation is rarely worth a confusing solution.

Tail calls — a JavaScript footnote

A tail call is a recursive call that is the very last action of a function. In theory, engines could optimise these to reuse the same stack frame — turning recursion into a loop under the hood. ES2015 specified "proper tail calls" (PTC) but only Safari implemented it. V8 and SpiderMonkey did not. In practice, do not rely on tail-call optimisation in JavaScript. If you would overflow the stack, switch to a loop.

Iterative factorial — safe for any n

JS
function factorial(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) result *= i;
  return result;
}

console.log(factorial(20));
A useful habit
When writing a recursive function, write the base case *first*. It forces you to answer "when do I stop?" before you tangle yourself in the recursive step.