Answers Built From Smaller Answers
Where the Recursion Stops
Last timeAssume the Smaller Case Is Done
The 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.
The half that is actually written
A recursion has two parts. One is assumed and one is written.
The combining step is the assumed part. It says what to do given an answer
that somebody else produced, and the previous lesson spent its whole length on
it. The smallest case is the written part. It is the only answer in the whole
method that is produced outright, from nothing, and therefore the only one
that can be wrong on its own terms rather than by inheriting an error.
It is also the part that gets about five seconds of attention, which is why
nearly every broken recursion is broken here.
Choosing which case to answer outright
The first decision is which case to treat as smallest, and there is usually
more than one defensible choice.
For adding up a list, the natural candidates are the empty list, whose total
is zero, and the single item list, whose total is that item. Both are correct
and the empty one is almost always better. It makes the combining step
uniform, since the single item case then falls out of the general rule rather
than being handled separately, and it removes a whole class of mistake around
inputs that are legitimately empty.
| empty case answer | handles an empty input | extra cases needed | |
|---|---|---|---|
| add up a list | 0 | 1 | 0 |
| multiply a list | 1 | 1 | 0 |
| longest word | 0 | 0 | 1 |
| reverse a list | 0 | 1 | 0 |
That marked row is worth dwelling on. Sometimes the empty case has no sensible
answer, and the honest thing is to say so rather than return something
plausible. A longest of nothing, a largest of nothing, an average of nothing:
these are not zero, they are questions with no answer, and returning zero
quietly turns a caller mistake into a wrong number that travels.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents