Recursion

Recursion is a technique where a function solves a problem by calling itself on a smaller version of the same problem. It is the natural fit for problems with a self-similar structure: trees, graphs, divide-and-conquer, and combinatorics.

The Two Required Parts

Every correct recursive function has a base case that stops the recursion and a recursive case that makes progress toward the base case. Missing either causes infinite recursion or a stack overflow.

function factorial(n) {
  if (n <= 1) return 1;         // base case
  return n * factorial(n - 1); // recursive case — n decreases each call
}

factorial(5); // 5 * 4 * 3 * 2 * 1 = 120

Thinking Recursively

The mental model: assume the function already works for smaller inputs and express the answer in terms of those smaller results. You do not need to trace every call stack level.

// Sum all numbers in a nested array — treat each element as a sub-problem
function deepSum(arr) {
  return arr.reduce((total, item) => {
    return total + (Array.isArray(item) ? deepSum(item) : item);
  }, 0);
}

deepSum([1, [2, [3, 4], 5]]); // 15

The Call Stack

Each recursive call adds a frame to the call stack. JavaScript's default stack depth is roughly 10,000–15,000 frames. Deep recursion on large inputs can exceed this limit.

// Stack overflow risk on large n:
function sum(n) {
  if (n === 0) return 0;
  return n + sum(n - 1); // 100,000 calls = stack overflow
}

// Iterative equivalent — no stack risk:
function sumIterative(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i;
  return total;
}

Memoization — Caching Repeated Work

Naive recursion recomputes the same subproblems. Memoization stores results and returns the cached value on repeated calls, turning exponential time into linear.

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

// Without memoization: O(2^n)
// With memoization:    O(n)

Tree Traversal — A Natural Recursive Problem

function treeSum(node) {
  if (node === null) return 0;
  return node.val + treeSum(node.left) + treeSum(node.right);
}

function maxDepth(node) {
  if (node === null) return 0;
  return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

Tail Recursion

A recursive call is in tail position when it is the very last operation — no work remains after the call returns. Some engines (not V8) optimise this into a loop, eliminating extra stack frames.

// Tail-recursive factorial using an accumulator
function factTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factTail(n - 1, n * acc); // last operation is the recursive call
}

When to Prefer Iteration

• When input can be arbitrarily large (stack overflow risk)
• When every level only processes one item (simple loops are faster)
• When the language/engine does not optimise tail calls

Use recursion when it makes the structure of the problem clearer — trees, graphs, divide-and-conquer — and iteration when it is equally clear but safer.