A First Taste of Algorithms · The Procedure That Calls Itself

Two halves are better than one smaller

Hanoi’s recursion shrank the problem by one — n hands work to n − 1 — and paid an exponential bill. Watch what happens to the bill when a recursion shrinks the problem by half.

The arena is sorting, and the lab equipment is a deck of cards. Take twenty, shuffled. The recursive plan, called merge sort:

split the pile into two halves; sort each half — somehow (you already know what fills in “somehow”); merge the two sorted halves into one sorted pile.

The floor: a pile of one card is already sorted.

Everything rests on the merge, so do it with your hands until it is boring. Two sorted piles face-up before you. The smallest card of all must be one of the two top cards — compare just those two, take the smaller, repeat. The merge never searches; it only ever looks at two cards and takes one, so combining piles of total size n costs about n cheap steps. Sortedness, once again, is purchased information — each pile’s order is exactly what lets one glance speak for the whole pile. (Chapter 1 said structure is bought in advance and collected later. Merge sort is a pyramid scheme of that idea that actually works: each level’s sortedness is collected from the level below, all the way down to single cards, which are sorted for free.)

Adding up the tree

Now the bill. Currency declared: element-steps, one for each time the merge touches a card. The cost C(n) of sorting n cards:

C(n) = 2·C(n/2) + n — two half-size sorts, plus a merge that touches everything once.

Don’t solve it with algebra. Draw it. The full job sits at the top: one box of size n. It opens into two boxes of size n/2; each opens into two of size n/4; and so on down to single cards. Now add up the merging cost level by level:

• Top level: one merge touching n cards → n.
• Next: two merges, each touching n/2 → n.
• Next: four merges of n/4 each → n.
• … every level totals exactly n.

So the whole bill is n per level, times the number of levels — and the number of levels is how many times n halves down to 1, which Chapter 1 taught you to name: log₂ n. Total:

C(n) ≈ n log₂ n.

A 7th grader’s arithmetic — sizes halve, level-sums stay flat, count the levels — and it tames one of the most important recurrences in computer science. Feel the number: a million cards cost about 1,000,000 × 20 = twenty million element-steps. Your laptop does that between two frames of a video. The obvious ways of sorting (Chapter 6 examines them, and people, sorting cards) cost around n² — for a million cards, a trillion steps, fifty thousand times more. Same problem, same answer, and the entire difference is that one procedure halves and the other plods. Hanoi shrank by one and hit the exponential wall; merge sort shrank by half and got the logarithm’s discount. Where a recursion sends its work is the whole game.

Figure 3.1 — The merge sort tree: every level’s merges touch n cards, and there are log₂ n levels.

Deeper water: the master theorem

The level-by-level tree settles any recurrence of the shape T(n) = a·T(n/b) + nᶜ — a subproblems, each a b-th of the size, plus nᶜ of local work — and the tree always tells one of exactly three stories. Compute the level sums: each level down, the work is multiplied by a/bᶜ.

• a/bᶜ < 1: level sums shrink geometrically; the top level dominates; T(n) ≈ nᶜ.
• a/bᶜ = 1: level sums stay flat (merge sort’s case, a = b = 2, c = 1); total = work-per-level × levels; T(n) ≈ nᶜ log n.
• a/bᶜ > 1: level sums grow; the bottom — the swarm of tiny cases — dominates; T(n) ≈ n^(log_b a).

That is the master theorem, minus rounding ceremony: every divide-and-conquer bill is a geometric series, and a geometric series is ruled by its ratio. (Book 2’s geometric series chapter was for this, among other things.) Test yourself: binary search is T(n) = 1·T(n/2) + 1 — which story, and does it agree with Chapter 1?

Deeper water: the stack is a physical object

When a procedure calls itself, the machine must remember every unfinished outer job while the inner one runs — Hanoi at n = 5 is paused, mid-sentence, while n = 4 works, which is paused while n = 3 works… The machine keeps these suspended jobs in a pile called the call stack: each call goes on top, finishes, comes off. (A pile where only the top is touched will get a name and a starring role in Chapter 5.) In Lab 3 you print each call indented by its depth, and the stack stops being a metaphor — you watch it breathe in and out on the screen.

The stack is physical: it occupies real memory, and it is finite. Python ships with roughly a thousand levels of patience, after which it raises RecursionError rather than drown — you will trigger this on purpose in the lab. And the floor-and-shrink rule from this chapter has a thunderclap hiding behind it: checking that your recursion terminates is usually easy, but could a procedure exist that inspects any program and decides whether it terminates? Hold the question; it is the Epilogue’s, and the answer is the strangest theorem you will ever meet.

Where this leaves us

A procedure may legitimately call itself, provided it always calls downward and the descent has a floor — and its correctness proof is then induction wearing work clothes. Its cost obeys a recurrence, and the recurrence is read from a tree: Hanoi’s tree doubles forever sideways and bills 2ⁿ − 1; merge sort’s tree halves quickly downward and bills n log₂ n. Same idea, opposite fates, decided entirely by where the recursion sends its work.

But there is a third fate, stranger than either, and Chapter 4 walks into it. Some recursions send their work to the same place twice — ask a perfectly honest question, and then, having forgotten the answer, ask it again, and again, millions of times. Such a recursion is correct, exponential, and wasting almost all of its effort on repetition — which means the exponential wall, for once, is made of paper. The fix is one idea: write the answers down. And the first thing the fix will do, in that chapter, is walk back into Sevenia and make change for 14 — correctly.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses