A First Taste of Algorithms · Recursion That Remembers

Write it down

The fix is one idea, and it is the entire chapter: the first time you answer a question, write the answer down; ever after, look it up.

The notebook for answers is a new tool, Python’s dictionary — a list, roughly, that you index by question instead of by position; Lab 4 introduces it properly. The memoized procedure (the term of art is memoization — “memo,” not “memor”: leaving yourself a memo) does this:

asked ways(n): if n is in the notebook, read it out; otherwise compute ways(n − 1) + ways(n − 2) — by this same procedure — write the result next to n in the notebook, then answer.

Now count the cost. Each of the n distinct questions is computed at most once — every later asking is a lookup. So the total computing work is about n. The audit in Lab 4 makes it brutal: ways(30) falls from 1.7 million calls to 57. Same recursion, same answers, same correctness proof. One notebook, and the exponential collapses to a straight line. There is no other moment in this book where so much is bought for so little.

And once the notebook is in view, a small liberation follows. The recursion fills the notebook from the top down — asked about 30, it scrambles down to the floor and climbs back. But you could just as well fill the notebook bottom-up: write ways(1), ways(2), then march upward, each entry a one-line sum of two earlier entries, no recursion at all, just a table and a loop. Top-down and bottom-up produce the identical table; they differ only in the order the blanks get filled (and bottom-up, having no call stack, never meets Chapter 3’s recursion limit). The table is the real object. The method that builds answers to a problem out of stored answers to its subproblems — by either route — is called dynamic programming, a name so unhelpful that it has its own story below. Think “recursion that remembers,” or just: the table method.

A human moment

“Dynamic programming” contains no dynamics and no programming in the modern sense. The name was chosen around 1950 by Richard Bellman at the RAND Corporation — and by his own telling, chosen as camouflage. The Secretary of Defense then funding RAND, Bellman wrote in his autobiography, “had a pathological fear and hatred of the word research”; mathematics was even worse. So Bellman picked a name no one could object to or even quite parse: “it’s impossible to use the word dynamic in a pejorative sense,” he explained, and “programming” then meant planning — schedules, logistics, tables — not code. Historians note the dates in his story don’t all line up, and Bellman, a famous raconteur, may have polished it. But the lesson survives the embellishment, and it is the second vignette in a row about a mathematician choosing a disguise: Lucas dressed an exponential as a toy from Siam; Bellman dressed a method as bureaucratic nothing to keep it funded. Names are not neutral. The thing itself — the table method — outlived the Secretary, the camouflage, and very possibly the anecdote.

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