Recursion

A function is recursive when it calls itself on a smaller version of the same problem. Trees, graphs, backtracking and dynamic programming are all recursion in some form, so it is worth getting comfortable first.

AnatomyCopy Anchor Link

Every recursive function needs:

1. A base case: an input so small the answer is immediate. Without it the function never stops.
2. A recursive case: solve the problem by calling yourself on a smaller input and combining the result.
3. Progress: each call must move toward the base case.

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

The call stackCopy Anchor Link

Each call waits on the stack until the call it made returns. factorial(3) runs as:

factorial(3) = 3 * factorial(2)
                    = 2 * factorial(1)
                          = 1

then unwinds: 1, then 2, then 6. A very deep recursion overflows the stack (RangeError: Maximum call stack size exceeded, roughly 10,000 frames in JavaScript). JavaScript engines do not optimise tail calls, so turn deep recursion into a loop or an explicit stack.

Reading the costCopy Anchor Link

Write the recurrence, then solve it.

Space is the depth of the stack: O(n) for factorial, O(log n) for binary search.

Common shapesCopy Anchor Link

• Linear: one call per step (sum of a list).
• Divide and conquer: split in halves, combine (merge sort).
• Tree recursion: one call per child (tree traversals, DFS).
• Backtracking: choose, recurse, undo.
• Overlapping calls: the same input is solved again and again. Cache results: see Memoization.

How to think about itCopy Anchor Link

Do not trace every call. Assume the function already works for smaller inputs and ask only: given those answers, how do I build mine, and what is the base case?

Common mistakesCopy Anchor Link

• Missing or wrong base case, giving infinite recursion.
• Not making progress (calling with the same input).
• Copying arrays on every call (slice, spread) and silently making it O(n²). Pass indexes instead.
• Recomputing overlapping subproblems (naive Fibonacci is O(2ⁿ)).

CodeCopy Anchor Link

export const sum = (arr, i = 0) => (i === arr.length ? 0 : arr[i] + sum(arr, i + 1));

export const power = (x, n) => { // O(log n): halve the exponent
  if (n === 0) return 1;
  const half = power(x, Math.floor(n / 2));
  return n % 2 ? half * half * x : half * half;
};

export const reverse = s => (s.length <= 1 ? s : reverse(s.slice(1)) + s[0]);

export const flatten = arr => arr.reduce((out, x) => out.concat(Array.isArray(x) ? flatten(x) : x), []);

export const fibSlow = n => (n < 2 ? n : fibSlow(n - 1) + fibSlow(n - 2)); // O(2^n)

export const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));

export const permutations = (items, path = []) => {
  if (!items.length) return [path];
  return items.flatMap((x, i) => permutations([...items.slice(0, i), ...items.slice(i + 1)], [...path, x]));
};