What is recursion?

JavaScript~3 min read

Recursion is a function that calls itself to break a problem into smaller versions of the same problem until it hits a base case it can solve directly.

Theory

TL;DR

Think of Russian nesting dolls: open one, find a smaller one inside, repeat until you reach the tiniest doll that has nothing inside.
Every recursive function needs two things: a base case (stop condition) and a recursive call (self-call with a smaller input).
Use recursion for trees, graphs, and nested structures. Use a loop for flat data to avoid stack overflow.
Node.js and browsers allow roughly 10,000 call stack frames before throwing RangeError: Maximum call stack size exceeded.

Quick example

javascript

function factorial(n) {
  if (n <= 1) return 1;        // base case: stop here
  return n * factorial(n - 1); // recursive call: smaller problem each time
}

console.log(factorial(5)); // 120
// Stack builds: factorial(5) -> 5 * factorial(4) -> ... -> 5 * 4 * 3 * 2 * 1

Each call adds a frame to the call stack. When factorial(1) hits the base case and returns 1, the stack unwinds. Each frame multiplies its n by the result below, working back to 120.

How the call stack handles this

V8 (Chrome/Node.js) pushes every recursive call onto the call stack as a new execution context with its own local variables. The frames sit there waiting until the base case fires. Then values unwind upward through each frame in reverse order.

The default stack depth in Node.js is around 10,000 frames. Exceed that and you get RangeError: Maximum call stack size exceeded. This is why factorial(100000) crashes, and why using recursion on large flat arrays is a bad idea.

When to use

Tree or graph traversal (DOM, file system, component trees): the structure is nested, so recursion maps to it directly.
Parsing nested data (JSON, HTML): each node can have children of the same shape.
Divide-and-conquer algorithms (quicksort, merge sort): the problem halves with each call.
Large flat arrays: use a loop instead. No nesting means no benefit, only stack risk.
Naive Fibonacci: fine for demos, but time complexity is O(2^n). Add memoization before shipping anything real.

Common mistakes

No base case:

javascript

function bad(n) {
  return n * bad(n - 1); // no stopping condition
}
// RangeError: Maximum call stack size exceeded

Fix: add if (n <= 1) return 1; before the recursive call.

Input not shrinking:

javascript

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n); // n doesn't change, infinite loop
}

Passing n instead of n - 1 is the most common mistake I've seen in code reviews. The function looks fine at a glance. Node.js only tells you something is wrong when the stack blows.

Fix: pass n - 1. Every call must move closer to the base case.

Ignoring stack depth: factorial(100000) crashes in Node.js. If the input can be large, use an iterative approach. You can bump the stack size with node --stack-size=65500, but that is a workaround, not a fix.

Real-world usage

React Fiber walks the component tree recursively during rendering (the reconciler goes depth-first).
Lodash _.flattenDeep recurses through nested arrays to fully flatten them.
Node.js directory walking uses recursive patterns to traverse folder hierarchies.
D3.js tree layouts recurse through node hierarchies to calculate visual positions.

Follow-up questions

Q: Write factorial as an iterative function.
A: function factIter(n, acc = 1) { if (n <= 1) return acc; return factIter(n - 1, acc * n); }. This is tail-recursive in form, but V8 does not optimize tail calls, so the stack still grows.

Q: What is the time complexity of naive Fibonacci recursion?
A: O(2^n). Each call branches into two more calls, so the total number of calls doubles at every level. Fix it with memoization or a bottom-up loop.

Q: Does JavaScript support tail call optimization?
A: No. V8 does not perform tail call optimization in practice. Even a correctly structured tail call still adds a frame to the stack. Use a loop for deep recursion.

Q: What happens to a recursive call stack if the user switches browser tabs mid-execution?
A: JavaScript is single-threaded. The browser pauses execution when the tab loses focus and resumes it on return. Heavy recursion that blocks the main thread freezes the UI until the stack fully unwinds. For expensive operations, use setTimeout or Web Workers to avoid blocking.

Examples

Basic: sum all numbers in an array

javascript

function sumArray(arr, index = 0) {
  if (index >= arr.length) return 0;            // base case: past the last element
  return arr[index] + sumArray(arr, index + 1); // add current, recurse on the rest
}

console.log(sumArray([1, 2, 3, 4])); // 10
// Unwinds as: 1 + (2 + (3 + (4 + 0)))

The base case fires when index equals the array length. From there, each frame returns its element plus everything to the right.

Intermediate: render a nested component tree

This is a simplified version of what React does when walking the component tree:

javascript

function renderTree(node) {
  if (!node.children || node.children.length === 0) {
    return `<div>${node.text}</div>`; // base case: leaf node, no children
  }

  let html = `<div>${node.text}`;
  node.children.forEach(child => {
    html += renderTree(child); // recurse into each child
  });
  return html + '</div>';
}

const tree = {
  text: 'App',
  children: [
    { text: 'Header', children: [] },
    { text: 'Main', children: [{ text: 'Article', children: [] }] }
  ]
};

console.log(renderTree(tree));
// <div>App<div>Header</div><div>Main<div>Article</div></div></div>

Iteration alone cannot handle arbitrary nesting depth cleanly. Recursion handles it in a few lines because the function does not need to know how deep the tree goes.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.

Finished reading?