Chapter 4 — Recursion + Sorting

"To understand recursion, you must first understand recursion."
That joke is actually a perfect definition. Let's make it precise.

Part 1: What Recursion Actually Is

Every function call you've ever made does three things:

1. Pushes a new stack frame onto the call stack in memory.
2. Executes the function body.
3. Pops the frame and returns the result to the caller.

When you write recursion, you're writing a function that, during step 2, calls itself — which means it pushes another stack frame before the first one is popped. And that second call might push a third. And so on.

Recursion is not magic. It is a function that does step 2 partially, calls itself, waits for the result, then finishes step 2.

Let's see this physically.

Part 2: The Call Stack — Physical Reality

The call stack is a region of memory. It grows downward in most CPU architectures. Every function call allocates a stack frame (also called an activation record), which stores:

• The function's local variables.
• The return address — where to jump when this function finishes.
• The arguments passed into this call.

Stack frames are pushed and popped in strict Last-In-First-Out (LIFO) order. That's why it's called a stack.

A concrete example — factorial:

function factorial(n) {
  if (n === 0) return 1;         // base case
  return n * factorial(n - 1);  // recursive case
}

factorial(4);

Let's trace the call stack frame by frame:

CALL factorial(4)
  Stack: [factorial(4)]  ← n=4, waiting for factorial(3)

  CALL factorial(3)
    Stack: [factorial(4), factorial(3)]  ← n=3, waiting for factorial(2)

    CALL factorial(2)
      Stack: [factorial(4), factorial(3), factorial(2)]  ← n=2, waiting for factorial(1)

      CALL factorial(1)
        Stack: [factorial(4), factorial(3), factorial(2), factorial(1)]  ← n=1, waiting for factorial(0)

        CALL factorial(0)
          Stack: [factorial(4), factorial(3), factorial(2), factorial(1), factorial(0)]
          n === 0  →  return 1   ← BASE CASE HIT. Stack frame popped.

        factorial(1) resumes: return 1 * 1 = 1.  Stack frame popped.
      factorial(2) resumes: return 2 * 1 = 2.  Stack frame popped.
    factorial(3) resumes: return 3 * 2 = 6.  Stack frame popped.
  factorial(4) resumes: return 4 * 6 = 24.  Stack frame popped.

Result: 24

Notice what happened: the entire chain of calls sat in memory simultaneously, waiting. At peak depth, there were 5 frames on the stack at once. That is the hidden cost of recursion — space proportional to the depth of the call stack.

Key insight: Recursion's space complexity is O(depth). A function that recurses n levels deep uses O(n) space — even if each frame is tiny.

Part 3: The Two Laws of Recursion

Every correct recursive function must have exactly two things:

Law 1: A base case — the condition where you stop recursing and return a direct answer.
Without a base case: infinite recursion → stack overflow → crash.

Law 2: A recursive case — the call to itself, with input that is strictly smaller (closer to the base case).
If the input doesn't shrink: infinite recursion → stack overflow → crash.

That's the whole contract. If you satisfy both laws, your recursion will terminate correctly.

For factorial:

• Base case: n === 0 → return 1 (we know the answer directly)
• Recursive case: factorial(n - 1) — n shrinks by 1 each call, guaranteed to reach 0

Part 4: The Recursive Leap of Faith

The hardest mental shift in recursion is this:

You do not need to trace the entire call tree in your head. You just need to trust that recursion(smallerProblem) returns the correct answer.

This is called the Recursive Leap of Faith (some call it the inductive hypothesis).

Here's how to use it for factorial:

• What does factorial(n) mean? It means: n multiplied by every positive integer below n.
• Assume factorial(n-1) is already correct — it returns (n-1)!.
• Then factorial(n) = n * factorial(n-1). Done.

You don't trace what factorial(n-1) does internally. You just trust it, the way you trust Math.sqrt() without reading its source code.

This is the mindset shift that unlocks recursion. Train your brain to:

1. Define what the function means (its contract/purpose).
2. Express the current call in terms of a smaller call of the same function.
3. Define where the chain stops (base case).

Part 5: How to Design a Recursive Solution — The Framework

For any recursive problem, answer these four questions in order:

Q1: What is the simplest version of this problem? → Base case.
Q2: What does f(n) mean? → Define the contract of your function.
Q3: If I trust that f(n-1) gives me the right answer, how do I use that to build f(n)? → Recursive case.
Q4: Does the input to the recursive call always shrink toward the base case? → Termination check.

Let's apply this to reversing a string:

Problem: Reverse a string recursively.
reverse("hello") → "olleh"

Q1: Simplest version? An empty string or single character is already reversed. Base case: if (s.length <= 1) return s;

Q2: What does reverse(s) mean? It returns s with all characters in reverse order.

Q3: If reverse(s.slice(1)) gives me "olleh" from "ello", how do I build reverse("hello")?
Answer: Take the first character "h" and append it at the end: reverse(s.slice(1)) + s[0].

Q4: Does s.slice(1) shrink toward the base case? Yes — every call removes one character. Reaches empty string in n steps. ✓

function reverse(s) {
  if (s.length <= 1) return s;           // base case
  return reverse(s.slice(1)) + s[0];     // recursive case
}

Dry run: reverse("abc")

reverse("abc")
  → reverse("bc") + "a"
    → reverse("c") + "b"
      → "c"              // base case
    → "c" + "b" = "cb"
  → "cb" + "a" = "cba"

Correct. And you never had to trace all three levels simultaneously — the leap of faith handled it.

Part 6: The Call Tree — Visualizing Branching Recursion

So far, recursion has been linear — each call makes exactly one recursive call. But recursion can branch.

Consider Fibonacci:

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Each call makes two recursive calls. The call tree for fib(5) looks like:

                     fib(5)
                   /         \
              fib(4)          fib(3)
             /      \        /      \
         fib(3)   fib(2)  fib(2)  fib(1)
         /   \    /   \   /   \
      fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
      /   \
   fib(1) fib(0)

Count the nodes: this tree has 2^(n+1) - 1 ≈ 2^n nodes for fib(n). Time complexity: O(2^n). Catastrophically slow.

Also notice: fib(3) appears twice. fib(2) appears three times. We are computing the same answers over and over. This is the waste — and it's what memoization (preview of Chapter 13, Dynamic Programming) fixes.

Key insight: The shape of the call tree IS the time complexity. Linear recursion → O(n) time. Binary branching recursion → O(2^n) time. This is not a rule — it's a consequence of counting nodes in the tree.

Part 7: Deriving Complexity — Recurrence Relations

For recursive algorithms, complexity analysis uses recurrence relations: a formula that describes the work done at the current level + the work delegated to recursive calls.

For a linear recursion like factorial:

T(n) = T(n-1) + O(1)

T(n) is the total work for input of size n. At each level we do O(1) work (the multiplication). We make one call on (n-1). Unrolling:

T(n) = T(n-1) + 1
     = T(n-2) + 1 + 1
     = T(n-3) + 1 + 1 + 1
     = ... (n times)
     = T(0) + n
     = n

Therefore: O(n) time, O(n) space (n frames on the stack).

For a branching recursion like Fibonacci:

T(n) = 2T(n-1) + O(1)

Each level doubles the number of calls, doing O(1) per call. This unrolls to O(2^n).

You'll derive more recurrences when we hit merge sort (the most important one). For now, internalize the pattern: write the recurrence, unroll it.

Part 8: Divide and Conquer — Merge Sort

Divide and conquer is the most powerful recursive technique. The pattern:

1. Divide — split the problem in half.
2. Conquer — recursively solve both halves.
3. Combine — merge the two solved halves into a full solution.

Merge sort is the canonical example. It is also one of the most important sorting algorithms in production (used in Python's timsort, Java's Arrays.sort for objects, and V8's Array.prototype.sort pre-Chrome 70).

The Idea

To sort an array:

1. Split it in half.
2. Sort the left half (recursively).
3. Sort the right half (recursively).
4. Merge the two sorted halves into one sorted array.

The key insight: merging two sorted arrays takes O(n) time — just walk both with two pointers, always picking the smaller front element.

Implementation

function mergeSort(arr) {
  // Base case: arrays of length 0 or 1 are already sorted
  if (arr.length <= 1) return arr;

  // Divide
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  // Conquer (recursive leap of faith: trust these return sorted arrays)
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);

  // Combine
  return merge(sortedLeft, sortedRight);
}

function merge(left, right) {
  const result = [];
  let l = 0, r = 0;

  // Walk both arrays, always pick the smaller front element
  while (l < left.length && r < right.length) {
    if (left[l] <= right[r]) {
      result.push(left[l]);
      l++;
    } else {
      result.push(right[r]);
      r++;
    }
  }

  // One array is exhausted — append the rest of the other
  while (l < left.length) result.push(left[l++]);
  while (r < right.length) result.push(right[r++]);

  return result;
}

Full Dry Run: mergeSort([5, 3, 8, 1])

Phase 1 — Divide until base cases:

mergeSort([5, 3, 8, 1])
├── mergeSort([5, 3])
│   ├── mergeSort([5])     → [5]    (base case)
│   └── mergeSort([3])     → [3]    (base case)
│   merge([5], [3])        → ?      (combine — see below)
└── mergeSort([8, 1])
    ├── mergeSort([8])     → [8]    (base case)
    └── mergeSort([1])     → [1]    (base case)
    merge([8], [1])        → ?      (combine — see below)
merge(?, ?)                → ?      (top-level combine)

Phase 2 — Combine step by step:

merge([5], [3]):

• l=0, r=0: left[0]=5, right[0]=3. 3 < 5 → push 3, r=1.
• r exhausted → push remaining left: push 5.
• Result: [3, 5]

merge([8], [1]):

• l=0, r=0: left[0]=8, right[0]=1. 1 < 8 → push 1, r=1.
• r exhausted → push remaining left: push 8.
• Result: [1, 8]

merge([3, 5], [1, 8]):

• l=0, r=0: left[0]=3, right[0]=1. 1 < 3 → push 1, r=1.
• l=0, r=1: left[0]=3, right[1]=8. 3 < 8 → push 3, l=1.
• l=1, r=1: left[1]=5, right[1]=8. 5 < 8 → push 5, l=2.
• l exhausted → push remaining right: push 8.
• Result: [1, 3, 5, 8] ✓

Phase 3 — Trace the call tree shape:

Level 0:       [5, 3, 8, 1]          ← 1 call, size 4
               /             \
Level 1:   [5, 3]         [8, 1]     ← 2 calls, size 2
           /   \           /   \
Level 2: [5]  [3]       [8]   [1]    ← 4 calls, size 1 (base cases)

The tree has log₂(n) levels (each level halves the size). At each level, the merge step touches every element once (O(n) total work per level). Therefore:

Total work = (work per level) × (number of levels)
           = O(n) × O(log n)
           = O(n log n)

This is not a fact you memorized. You derived it from the tree structure.

Space complexity: The call stack depth is O(log n) (log levels of recursion). The merge function creates new arrays — at any moment, O(n) extra space is in use. So space = O(n).

Why merge sort beats O(n²) algorithms

Selection sort, insertion sort, bubble sort: all O(n²). Why? Because they don't divide. Each element is compared against all others in the worst case.

Merge sort's trick: sorted subarrays can be merged in O(n) — you only need one pass because you already know both halves are sorted. Every divide-and-conquer that achieves O(n) merging will deliver O(n log n).

The mathematical lower bound: You cannot sort a general array in better than O(n log n) time using comparisons. Merge sort is optimal in this sense.

Part 9: Quicksort — Partition Instead of Merge

Quicksort is the other dominant O(n log n) sort. It's in-place (no extra array), which is why it often outperforms merge sort in practice despite the same asymptotic complexity.

The idea: Instead of dividing evenly then merging, pick a pivot element, then partition the array so everything smaller is left of the pivot and everything larger is right. Then recursively sort both sides.

The partition step is O(n). After partitioning, the pivot is in its final sorted position — permanently. You never need to move it again.

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low >= high) return;  // base case: 0 or 1 elements

  const pivotIndex = partition(arr, low, high);
  quickSort(arr, low, pivotIndex - 1);   // sort left of pivot
  quickSort(arr, pivotIndex + 1, high);  // sort right of pivot
}

function partition(arr, low, high) {
  const pivot = arr[high];  // choose last element as pivot
  let i = low - 1;          // i tracks the boundary of "smaller" region

  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];  // swap into "smaller" region
    }
  }

  // Place pivot at its final position
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;  // pivot's final index
}

Dry run: quickSort([3, 1, 4, 2])

• low=0, high=3. pivot=arr[3]=2. i=-1.
  • j=0: arr[0]=3 > 2. Skip.
  • j=1: arr[1]=1 ≤ 2. i=0. Swap arr[0] and arr[1]: [1, 3, 4, 2].
  • j=2: arr[2]=4 > 2. Skip.
  • Place pivot: swap arr[i+1]=arr[1] and arr[high]=arr[3]: [1, 2, 4, 3]. pivotIndex=1.
• Pivot 2 is now at index 1. Permanently placed. ✓
• quickSort([1]) → done (low >= high).
• quickSort([4, 3], low=2, high=3):
  • pivot=3. i=1.
    • j=2: arr[2]=4 > 3. Skip.
    • Place pivot: swap arr[2] and arr[3]: [1, 2, 3, 4]. pivotIndex=2.
  • quickSort([]) → done. quickSort([4]) → done.
• Final: [1, 2, 3, 4] ✓

Complexity of quicksort:

• Best/average case: pivot lands near the middle each time → O(n log n). (Same tree shape as merge sort.)
• Worst case: pivot is always the smallest or largest element (already-sorted input with naive pivot choice) → O(n²). The "tree" becomes a linked list.

This is why production implementations use random pivots or median-of-three pivot selection — to avoid the worst case on common inputs.

Key difference from merge sort:

• Merge sort: divide evenly, work during combine.
• Quicksort: work during divide (partition), no combine needed.
• Both: O(n log n) average. Merge sort is O(n log n) worst case. Quicksort is O(n²) worst case.
• In practice: quicksort is faster due to cache locality (in-place) and lower constant factors.

Part 10: The Space Cost Nobody Talks About

Recursion always costs stack space. This matters more than most people realize.

Scenario: recursive binary search on 1 billion elements.

Binary search is O(log n) time. log₂(1,000,000,000) ≈ 30. So the recursive version uses 30 stack frames. Each frame maybe 100 bytes. Total: ~3KB. Fine.

Scenario: recursive linear scan on 1 million elements.

Linear recursion is O(n). 1,000,000 stack frames × ~100 bytes = 100MB. Stack overflow well before that — Node.js default stack is ~10MB, allowing ~10,000-15,000 frames.

// This will crash for n > ~10,000
function sum(n) {
  if (n === 0) return 0;
  return n + sum(n - 1);
}
sum(100000);  // RangeError: Maximum call stack size exceeded

The rule: Use recursion when depth is O(log n) or small and bounded. Switch to iteration when depth is O(n).

For the sum example, the iterative version is:

function sum(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i;
  return total;
}

This is O(n) time, O(1) space — clearly better.

Part 11: Tail Recursion

Tail recursion is when the recursive call is the very last thing the function does — nothing happens after the return value comes back.

// NOT tail recursive — must multiply after returning
function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);  // ← must wait for result, then multiply
}

// Tail recursive — accumulator carries state, last operation is pure call
function factorialTail(n, acc = 1) {
  if (n === 0) return acc;
  return factorialTail(n - 1, n * acc);  // ← last operation is the call itself
}

In the tail recursive version, nothing needs to happen after factorialTail(n-1, n*acc) returns. The caller doesn't need to exist anymore. A smart runtime can reuse the same stack frame instead of pushing a new one — this is Tail Call Optimization (TCO). Result: O(1) space instead of O(n) space.

JavaScript reality: TCO is specified in ES6 but only implemented in Safari. Node.js and Chrome V8 do NOT implement TCO. So in JavaScript, tail recursive code is stylistically cleaner but doesn't save stack space in practice.

Practical rule for JS: Don't rely on TCO. For O(n)-depth recursion, convert to iteration manually.

Part 12: Mental Model — When to Reach for Recursion

Reach for recursion when:

1. The problem has natural self-similar substructure. A tree node's behavior is the same as all its children's behavior. A directory contains other directories.

2. You can define f(n) in terms of f(smaller n). If you can write the solution to the big problem as "use the solution to a smaller version of the same problem," recursion is the right shape.

3. The depth is bounded and small (ideally O(log n) or a small constant). Tree height, divide-and-conquer levels, backtracking depth with good pruning.

4. The code is dramatically simpler than the iterative equivalent. Tree traversal in 3 lines vs. explicit stack management in 20 lines.

Do NOT reach for recursion when:

1. The depth is O(n) and n is large. Use iteration — you'll hit the stack limit.
2. You're recomputing the same subproblems. Use memoization or dynamic programming.
3. The iterative version is equally simple. Iteration has zero stack overhead.

Part 13: Real Systems — Recursion in Production

V8's call stack:
Node.js and Chrome run on V8. The default call stack depth in Node.js is ~10,000-15,000 frames. You can see this with node --stack-size=65536 to increase it. Every time you write a deeply nested callback chain or deeply recursive function, you're consuming V8's call stack.

When V8 throws RangeError: Maximum call stack size exceeded, it's because it exceeded the physical memory limit for the call stack region.

Node.js stack traces:
Every Error.stack you see is a snapshot of the call stack at that moment — from the deepest frame (where the error was thrown) up to the outermost frame. Recursive calls appear as repetitions in the stack trace. If you ever see the same function repeated 20 times in a stack trace, that's recursion — often infinite recursion that got cut off.

React's reconciler (Fiber):
React 15 used recursive tree traversal to reconcile the virtual DOM. Deep component trees caused call stack overflows and blocked the main thread (no pausing in the middle of a recursive function). React 16 rewrote the reconciler ("Fiber") to use an iterative, explicit work queue instead — so it could pause, yield, resume, and prioritize work. The insight: convert O(depth) recursion to O(1) call-stack iteration, managing the "where I am" state explicitly.

File system traversal (Node.js fs):
fs.readdir + recursion is the natural way to walk a directory tree. But for very deep directory trees, Node.js limits apply. Production tools like glob and fast-glob use iterative BFS with explicit queues instead.

PostgreSQL query planner:
SQL JOINs form a tree. The query planner uses recursive algorithms to explore different join orderings and estimate which plan is cheapest. For complex queries with many tables, the exponential explosion of join orderings is why very complex queries take a long time to plan.

Browser DOM traversal:
The DOM is a tree. Browsers implement querySelector, event bubbling, CSS inheritance, and layout computation via tree traversal — which is essentially recursive. The browser's internal implementation uses an iterative stack (for performance and stack depth reasons) but the logic is identical to recursive tree traversal.

Part 14: Vocabulary Map

Part 15: 5 Practice Problems

1. Trace and Predict

function mystery(n) {
  if (n <= 0) return 0;
  return mystery(n - 3) + n;
}

Trace mystery(9). Draw every stack frame. What is the return value? What are the base case and recursive case? What is the time and space complexity? What does this function compute mathematically?

2. Find the Waste

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Trace fib(6). Count how many times fib(3) is called. How many times is fib(2) called? What is the total number of calls? Where is the waste? What data structure would eliminate it, and what would the complexity become?

3. Failure Analysis

A junior engineer writes:

function flatten(arr) {
  for (let item of arr) {
    if (Array.isArray(item)) {
      flatten(item);  // handle nested array
    }
  }
}

Identify every bug. The function is supposed to return a flat array (e.g., flatten([1, [2, [3, 4]], 5]) → [1, 2, 3, 4, 5]). Write the correct version.

4. Design Under Constraints

You need to compute sum(n) = 1 + 2 + ... + n recursively. First write the naive version. Then identify why it fails for n = 100,000. Then convert to a tail-recursive version. Then explain why in Node.js the tail-recursive version still fails and write the iterative solution.

5. Reach Beyond

You have a function mergeSort that correctly sorts an array. Now write kthSmallest(arr, k) that returns the k-th smallest element without fully sorting, using a partition-based approach (similar to quicksort's partition). What is the average time complexity? What is the worst case? (This is the quickselect algorithm — used in ORDER BY ... LIMIT k optimizations in databases.)

Connect Forward

Chapter 4a attacks the top recursion interview problems: Fibonacci with memoization (first taste of DP), Power function, Subsets (every element: include or exclude — the foundation of backtracking), and Merge Sort implementation from scratch.

After Chapter 4a, you're ready for Chapter 5 (Two Pointers) — a technique that is essentially iterative but whose correctness proof is often recursive in structure.

The bigger payoff comes later: Chapter 10 (Trees) and Chapter 12 (Graphs) are almost entirely recursive. Chapter 11 (Backtracking) is recursion with pruning. Chapter 13 (Dynamic Programming) is memoized recursion. Everything built from Chapter 4 forward.

Connect Backward

Chapter 2 (Arrays) gave you the underlying physical structure — contiguous memory, O(1) access by index. Merge sort uses that: arr.slice() is O(n) because it must copy elements to a new contiguous block.

Chapter 3 (HashMaps) preview: the memoization table in Fibonacci is a HashMap. memo[n] = result. That's all memoization is — caching function outputs by input using a HashMap.