Recursion patterns and the recursion tree

Draw the calls as a tree and the complexity reads straight off it: cost = number of nodes × work per node, and the depth is the space.

Linear recursion — one call per level

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

n nodes in a chain: O(n) time, O(n) stack. A loop does this in O(1) space.

Binary recursion — two calls per level

const fib = (n) => (n < 2 ? n : fib(n - 1) + fib(n - 2));

The tree branches twice per level to depth n: roughly 2ⁿ nodes. fib(40) is over a billion calls, and most of them recompute values already computed. That redundancy is exactly what memoisation removes, and it is the doorway to dynamic programming.

Divide and conquer — two calls on halves

const mergeSortCost = 'T(n) = 2T(n/2) + O(n)';   // → O(n log n)

Also two branches, but each works on half the input, so there are log n levels with n work each. The difference between this and fib is what the recursive call receives, not how many calls there are.

Multi-branch recursion — k calls per level

Permutations branch n ways, then n−1, then n−2: O(n!) leaves. Subsets branch twice per element: O(2ⁿ). These are backtracking's territory, and they are only viable for small n.

The Master Theorem, briefly

For T(n) = a·T(n/b) + O(nᵈ):

Turning a recursion into a memoised one

const fibFast = (n, memo = new Map()) => {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);

  const value = fibFast(n - 1, memo) + fibFast(n - 2, memo);
  memo.set(n, value);
  return value;
};

Two lines turn O(2ⁿ) into O(n): each distinct argument is computed once. If your recursion tree repeats subproblems, this is always the first thing to try.