Basis Lab

Making it fast enough

Solve a problem by assuming the smaller version is already solved, notice when that assumption makes you solve the same small version thousands of times, and remove the repetition so that an impossible search becomes a table you fill once

Answers Built From Smaller Answers

Recursion, and the two repairs that turn it from elegant to practical. The road from a function that calls itself to a table filled bottom up.

8 lessons, written and corrected before you arrived. Reading them here needs no account. The first reads the whole way through; the others open and then stop, because a page nobody owns cannot tell who is reading it. Starting the course gives you your own copy, where every idea has problems standing under it and you can ask about any sentence.

Start reading

This is course 4 of 8 in a reading track: tell in advance which approach survives a million rows. The track is an order, not a gate, and the rest of it is on one page.

  1. 01Assume the Smaller Case Is DoneA problem becomes easy the moment you are allowed to assume the slightly smaller version is already answered, and the only work left is the step that combines.
  2. 02Where the Recursion Stopsopening onlyThe smallest case is the half of a recursion that is written carelessly, and almost every recursion that fails does so because of what it says or forgets to say there.
  3. 03What the Machine Is Holding While It Waitsopening onlyEvery unfinished call is being held somewhere while it waits for the one inside it, and the pile of them is the memory cost nobody writes down when they write the three lines.
  4. 04Splitting the Work in Halfopening onlyShrinking a problem by one gives a method as slow as the loop it replaced, and shrinking it by half gives something qualitatively different for the same three lines.
  5. 05Solving the Same Thing Over and Overopening onlyWhen a recursion calls itself twice, the two branches ask many of the same questions, and the number of times one small question is asked grows out of control.
  6. 06Writing Each Answer Down Onceopening onlyKeep every answer the moment it is computed and return it when asked again, and the tree of calls collapses to one call per distinct question.
  7. 07Working Bottom Up Insteadopening onlyTurn the remembered recursion inside out, fill the answers in order from the smallest up, and the recursion disappears along with the pile of waiting calls.
  8. 08When You Do Not Need the Tableopening onlySome problems are solved by taking the best looking step each time, with no table and no recursion, and the difficulty is that the ones that are not look exactly the same.