Skip to main content

Recursion and divide-and-conquer — throwing a large problem back at a smaller self

Traversing directories inside directories, however deep. Counting how many people report through the org chart. Problems where "the same shape is nested inside itself" get awkward in loops.

Recursion is the tool for writing that nesting the way the structure looks. And turning the same idea toward "take a non-nested problem and nest it yourself" gives you divide-and-conquer.

What you'll learn in this chapter​

  • Designing recursion as base case and recursive step
  • Drawing a recursion tree to count work and depth
  • The call stack consumes space — when to choose iteration
  • Divide-and-conquer patterns, and merge sort vs. quicksort
  • Situations that require stable sort
Prerequisites

Builds on big-O and time/space complexity from Complexity. Having read Binary search makes the divide-and-conquer section land faster.

Recursion is made of two parts​

A recursive function needs only two things.

PartRole
Base caseThe smallest input that isn't decomposed further. Recursion stops here
Recursive stepCall itself with an input that is strictly smaller

Factorial:

function factorial(n: number): number {
  if (n === 0) return 1;      // Base case
  return n * factorial(n - 1); // Recursive step (n decreases by 1)
}

What matters in design is order. Decide "where does it stop" first, then "how does it get smaller". Reverse this and you'll produce non-terminating recursion.

What happens if it doesn't stop​

Running a function that forgot its base case:

function depth(n: number): number {
  return depth(n + 1); // No base case, and n is increasing
}
depth(0);
// RangeError: Maximum call stack size exceeded

This limit isn't defined by the language spec. It's implementation-dependent — decided by how much call stack the engine can hold. Even the error name differs: V8 and Safari throw RangeError: Maximum call stack size exceeded; Firefox throws InternalError: too much recursion.

Measured on Node.js, it dies around 10,000 frames. More local variables per frame reduces this. Rather than memorizing "how many levels are safe", avoid recursion whose depth grows with input size — that's the reliable rule.

Counting work with a recursion tree​

The complexity of recursion is estimated as depth × work per level, from the tree of calls.

Fibonacci written by definition:

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // Two branches per call
}

Each call branches twice; the depth is n. The number of nodes in the tree grows exponentially. Counting calls makes the growth clear.

let calls = 0;
function fib(n: number): number {
  calls++;
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}
for (const n of [10, 20, 30]) {
  calls = 0;
  fib(n);
  console.log(`fib(${n}) calls: ${calls}`);
}
// fib(10) calls: 177
// fib(20) calls: 21891
// fib(30) calls: 2692537

Adding 10 to n multiplies by about 123. Recursion that branches is exponential — take this as a rule.

The upper bound is 2ⁿ from the branch count, but because one branch is one shallower, the actual growth is milder — about 1.62ⁿ (the golden ratio φ ≈ 1.618). The "123× per 10" figure corresponds to φ to the 10th. Using the upper bound as-is overestimates, and the gap widens with n (about 6× at n = 10, 48× at 20, 400× at 30), so when counting the tree, account for the branch depth difference.

fib(3) appears twice, fib(2) three times. The exponential is because the same arguments are recomputed. Noticing this is the entrance to dynamic programming.

One branch means not exponential. Factorial and binary search have one branch, so the tree is a single line. Count the branches first.

The call stack consumes space​

Recursive calls stack up because return addresses must be remembered. The depth simultaneously on the stack is the space complexity.

StyleTimeSpace
Binary search (iterative)O(log n)O(1)
Binary search (recursive)O(log n)O(log n)

Same algorithm, different space. As covered in the Binary search chapter, when writing complexity, don't forget to count the call stack.

O(log n) depth isn't practically a problem — 20 frames at 1,000,000 items. Dangerous is depth proportional to n, which happens when recursively traversing a 100,000-item list one at a time.

Divide-and-conquer — split, solve, merge​

Beyond "recursing through nested structure", taking a non-nested problem and dividing it yourself is divide-and-conquer. The pattern is three steps.

  1. Divide — cut the input into smaller chunks
  2. Solve — recursively solve each chunk
  3. Merge — combine partial answers into the whole

Binary search is a special case. After halving, only one half is solved and no merging is needed. That's why it's O(log n).

Merge sort — the work is in merging​

Splitting is just cutting in the middle; the work is on the merge side.

function mergeSort(xs: number[]): number[] {
  if (xs.length <= 1) return xs; // Base case: length ≤ 1 is sorted
  const mid = Math.floor(xs.length / 2);
  const left = mergeSort(xs.slice(0, mid));
  const right = mergeSort(xs.slice(mid));
  return merge(left, right);
}

function merge(a: number[], b: number[]): number[] {
  const out: number[] = [];
  let i = 0;
  let j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) out.push(a[i++]); // Take left first on ties = stability condition
    else out.push(b[j++]);
  }
  return out.concat(a.slice(i)).concat(b.slice(j));
}

console.log(mergeSort([5, 3, 8, 1, 9, 2, 7]).join(","));
// 1,2,3,5,7,8,9

Complexity comes from depth × work per level. Halving gives log₂ n depth; each level merges every element once, so O(n). Multiplied: O(n log n).

Extra memory is O(n) — each merge creates a new array.

Quicksort — the work is in dividing​

Split into the group smaller than a pivot and the group larger. Merging is just concatenation.

function quickSort(xs: number[]): number[] {
  if (xs.length <= 1) return xs;
  const pivot = xs[xs.length - 1];
  const rest = xs.slice(0, -1);
  const smaller = rest.filter((x) => x < pivot);
  const larger = rest.filter((x) => x >= pivot);
  return [...quickSort(smaller), pivot, ...quickSort(larger)];
}

console.log(quickSort([5, 3, 8, 1, 9, 2, 7]).join(","));
// 1,2,3,5,7,8,9

The above prioritizes readability, so it's a non-in-place version. Each level creates new arrays with filter and spread, so extra memory isn't O(log n) as in the table. The table's values are for the in-place version — swapping within the array — where extra memory is the recursion depth: O(log n) when the splits are even, growing to O(n) in the worst case where they skew to one side.

Pivot choice decides performance. Splitting exactly in half every time gives depth log₂ n and O(n log n). But taking the last element as pivot on already-sorted input makes one side always empty, depth grows to n, and it degrades to O(n²).

Merge sortQuicksort
Time (average)O(n log n)O(n log n)
Time (worst)O(n log n)O(n²)
Extra memoryO(n)Average O(log n) / worst O(n) (recursion depth)
StabilityStableUnstable

Avoid worst case → merge sort; save memory → quicksort. Language and library built-in sorts often combine several methods rather than using either directly.

When stable sort is needed​

Stable means when comparing equals, the original order is preserved.

type Row = { name: string; score: number };
const rows: Row[] = [
  { name: "a", score: 1 }, { name: "b", score: 2 }, { name: "c", score: 1 },
  { name: "d", score: 2 }, { name: "e", score: 1 },
];
const sorted = [...rows].sort((x, y) => x.score - y.score);
console.log(sorted.map((r) => r.name).join(""));
// acebd

The three items with score 1 come out as a, c, e; the two 2s as b, d. Both preserve original order.

This matters when sorting by composite keys. To sort "by department, then by hire date within department", sort by hire date first, then by department — one comparator gives two levels of ordering. Without stability, the later sort destroys the earlier.

JavaScript's Array.prototype.sort is required by ECMAScript 2019 onward to be stable. Before that it was engine-dependent.

warning

Omit the comparator and sort converts elements to strings and compares by UTF-16 code unit order. [1, 30, 4, 21, 100000].sort() yields [1, 100000, 21, 30, 4] for this reason. Always pass a comparator for numbers.

Decision procedure​

Recursion vs. iteration​

SituationChoose
Data itself is nested (trees, directories, JSON)Recursion. Structure and code match, easy to read
Depth grows with the number of items (list, one at a time)Iteration. Stack overflows
Depth stays within log n (halve each round)Either. Iteration only when tight on space
Branches into repeated same argumentsMemoize the recursion, or convert to a table

Estimation once you decide "sort first"​

Any step in your procedure that sorts by comparison makes the whole thing bounded by O(n log n). Comparing elements to sort can't beat O(n log n), no matter the technique.

Exception: when the value range is limited — 0-to-100 scores, dates, fixed-digit IDs — "counting the values" without comparison brings it to O(n). This lower bound applies only to comparison-based sorting.

For example, "remove duplicates then return the top 10" written as "sort then compare adjacent" is O(n log n). Same thing with a Set is O(n). Same judgment as "watch for hidden loops" in Complexity — treat sorting as a hidden O(n log n).

Conversely, sorting once and then running binary searches many times amortizes the sort cost. For a single lookup, linear search can be faster.

Common misconceptions​

"Recursion is slower than loops." — There's call overhead, but the order doesn't change. Slowness comes from re-solving the same arguments repeatedly. That's not recursion's fault — it's not collapsing the overlap.

"Tail recursion is safe to go deep with." — Tail call optimization is in the ECMAScript spec, but major engines don't broadly implement it. In Node.js (V8), recursion written tail-recursively still hits RangeError at the same order of frames (measured around 7,000 — a bit shallower than the ~10,000 in the main text, because one accumulator argument grows the frame). Assume recursion whose depth grows with input crashes even if tail-recursive.

"Quicksort is faster than merge sort." — By constant factors on average, yes, but worst-case is O(n²). When input is near-sorted, positions flip.

"Stability is a minor detail." — For composite-key sorts, it changes the result. Code that splits sorting in two depends on stability.

Exercises​

Q1. A function counting people in the org chart hits RangeError on 50,000-employee data. The tree depth is at most 12 levels. What do you suspect?

Answer and explanation

Answer: Suspect not the tree-walking recursion but a place recursing over a list of colleagues one at a time.

Depth 12 doesn't overflow the stack — you can stack around 10,000 frames. Recursing a depth-12 tree stacks at most 12 frames.

The RangeError implies there's another recursion whose depth grows with item count. Two common shapes:

  • Splitting an array into "first + rest" and recursing. 50,000 items → 50,000 frames
  • The tree has cycles and revisits the same node (a parent registered as a child)

Triage: pass the current depth to the recursive function and abort with info if it exceeds a threshold. If depth approaches item count, it's the first case; if the same node name repeats, the second.

Depth is decided by the shape of the data, not the item count. Confuse these and you look at the tree's levels and wrongly conclude "safe".

Q2. Sort a product list "by category, then by ascending price within category". You split sorting into two. Which do you do first?

Answer and explanation

Answer: Price first, category second.

In a stable sort, the later applied order becomes the outer order. Put the higher-priority key last.

const sorted = [...items]
  .sort((a, b) => a.price - b.price)            // Inner order
  .sort((a, b) => a.category.localeCompare(b.category)); // Outer order

Sorting by category first, then price, destroys the category ordering.

This style depends on stability. Combining into one comparator that first compares category and then price on ties avoids the stability dependence and traverses once. Splitting into two is fine only when keys are dynamic and hard to combine.

Q3. Sorting 10 million records with merge sort ran out of memory. Does switching to quicksort solve it?

Answer and explanation

Answer: Extra memory decreases but at the cost of worst-case risk. If the entire set doesn't fit in memory, neither solves it.

Split the judgment in two.

Stage 1 — does everything fit in memory? If not, the choice of sort algorithm doesn't solve it. You need to split data into chunks, sort each, and merge the sorted chunks. That merge is exactly the merge from the text — just the "merge" from divide-and-conquer pulled outside.

Stage 2 — if it fits, does the extra-memory difference matter? Merge sort needs O(n) for the merge target; quicksort, in the in-place version that swaps within the array, needs the recursion depth — O(log n) when the splits are even, O(n) when they skew. At 10 million, the difference is large and may fit. The quicksort in the text is a non-in-place version, so porting it as-is doesn't reduce memory.

But there's a cost. Quicksort's worst-case is O(n²). Near-sorted data — daily-appended logs, records fetched by primary key — hits this worst case easily. Randomizing pivots or estimating the median reduces probability but doesn't eliminate.

Stability is also lost. If you split composite-key sorting in two, results change.

Summary​

  • Recursion is base case + recursive step. Decide where it stops first
  • The depth limit is not language-defined; implementation-dependent. About 10,000 in Node.js measurement
  • Complexity is estimated as recursion tree depth × work per level. Branching two ways or more is exponential
  • Count the call stack as space complexity. Iterate when depth is proportional to item count
  • Divide-and-conquer is divide, solve, merge. Binary search is the special case "only one half solved, no merge"
  • Merge sort is worst-case O(n log n), stable, with O(n) extra memory. Quicksort is worst-case O(n²), unstable, with O(log n) extra memory on average
  • Stable sort changes results when sorting by composite keys. Apply the higher-priority key last
  • Array.prototype.sort is required by ECMAScript 2019+ to be stable. Omitting the comparator gives string comparison
  • A comparison sort in the procedure bounds the whole thing at O(n log n). With a limited value range, non-comparison counting brings it to O(n)
Related references