Recursion

Functions that call themselves - the natural fit for tree traversal, with a hard stack limit that matters on user-supplied data.

A recursive function is one that calls itself. Every recursion needs a base case (the condition where the function stops calling itself) and a recursive step that shrinks the problem toward that base case.

Factorial is the textbook example. The base case is n <= 1 (return 1). The recursive step multiplies n by the factorial of n - 1, which is a smaller version of the same problem.

function factorial(n) {
  if (n <= 1) return 1;       // base case: stop here
  return n * factorial(n - 1); // recursive step: smaller problem
}
 
console.log(factorial(1)); // 1
console.log(factorial(4)); // 24  (4 * 3 * 2 * 1)
console.log(factorial(6)); // 720
 
// Call stack for factorial(4):
// factorial(4) -> 4 * factorial(3)
//                     -> 3 * factorial(2)
//                            -> 2 * factorial(1)
//                                   -> 1  (base case)

Recursion is the natural shape for traversing nested structures like trees or deeply nested objects. Each level of nesting becomes one level of recursion. An iterative loop would need to track depth manually.

const fileTree = {
  name: "src",
  children: [
    { name: "index.js", children: [] },
    {
      name: "utils",
      children: [
        { name: "math.js", children: [] },
        { name: "string.js", children: [] },
      ],
    },
  ],
};
 
function printTree(node, depth = 0) {
  const indent = "  ".repeat(depth);
  console.log(indent + node.name);
  for (const child of node.children) {
    printTree(child, depth + 1); // same function, smaller problem
  }
}
 
printTree(fileTree);
// src
//   index.js
//   utils
//     math.js
//     string.js

For bounded inputs, an iterative loop and a recursive function are equally readable. The loop version avoids function call overhead and is sometimes clearer when the problem is simply counting down.

// Recursive factorial
function factorialRecursive(n) {
  if (n <= 1) return 1;
  return n * factorialRecursive(n - 1);
}
 
// Iterative equivalent - no stack frames, same result
function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}
 
console.log(factorialRecursive(6));  // 720
console.log(factorialIterative(6));  // 720

In production

V8 does not optimize tail calls, so every recursive call adds a stack frame. In practice, Node.js and most browsers throw a RangeError: Maximum call stack size exceeded at around 10,000 to 15,000 frames. If the input comes from a user (a deeply nested JSON document, a large file tree, user-submitted HTML), recursion will blow the stack. Convert to an iterative approach using an explicit stack (const stack = [root]; while (stack.length) { ... }) whenever depth is unbounded. Recursion is safe for compile-time-bounded structures like AST visitors over a grammar you control.

← PreviousHigher-Order Functions and Callbacks Next →Maps and Sets

Enjoyed this? Get more essays on software craft delivered to your inbox.

Subscribe free