Assume the Smaller Case Is Done

A 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.

A strange kind of permission

Here is a problem. Add up a list of a thousand numbers.

Here is a way to make it easy. Assume somebody has already added up the last

nine hundred and ninety nine of them and handed you the total. Now your whole

job is to add the first number to what they gave you. One addition.

That sounds like cheating, and the first reaction is usually to ask who added

up the nine hundred and ninety nine. The answer is that they used the same

permission: they assumed somebody had added up the last nine hundred and

ninety eight, and did one addition. And so on down.

The permission is not a trick. It is the whole method, and it is worth

noticing how much it removes. The problem of adding a thousand numbers has

become the problem of writing one addition and saying what happens when the

list is empty. Nothing else needs to be worked out, held in mind, or traced.

FIG 1The assumption, written out

python

def total(xs):
    if not xs:
        return 0  # the smallest case, answered outright
    return xs[0] + total(xs[1:])  # assume the rest is already added up
print(total([4, 8, 15, 16, 23, 42]))  # 108
def longest(words):
    if len(words) == 1:
        return words[0]
    rest = longest(words[1:])  # assume the longest of the rest is known
    return words[0] if len(words[0]) > len(rest) else rest
print(longest(["pin", "thread", "board", "needle"]))  # needle

Both methods are three lines and neither contains a loop, a counter or an index. The second one is worth reading twice: it never compares more than two words at a time, because the comparison it needs is between the first word and the single answer for everything else.

Why the assumption is allowed

The uneasy feeling is worth taking seriously, because the assumption looks

circular. It is not, and the reason is that each use of it is applied to a

strictly smaller problem than the one before.

Think of it as a claim rather than as a procedure. The claim is: if the method

works on inputs of size $n - 1$ , then it works on inputs of size $n$ . The

combining step is the proof of that claim. Separately, the method is checked

by hand on the smallest case. Those two facts together mean the method works

on every size, by the same reasoning that makes a row of dominoes fall: the

first one goes over, and each one knocks over the next.

FIG 2What a recursive definition actually asserts

: the method gives the right answer on every input of size n

The left hand side has two parts and they map exactly onto the two parts of the code. The first is the smallest case answered outright, which the next lesson is about. The second is the combining step. Checking a recursion means checking those two things, and nothing else.

This also explains why unrolling a recursion in your head is the wrong way to

read one. Following a thousand nested calls is impossible and following three

proves nothing. The useful reading is the claim: assuming the inner answer is

right, is the combining step right? That question can be answered in a few

seconds and it covers every size at once.

Choosing what smaller means

The hard part is not writing the combining step. It is deciding what smaller

is going to mean, because different choices lead to completely different

methods, and some choices lead nowhere at all.

For a list, the obvious smaller is the list without its first item. But the

list without its last item is also smaller, and so are the two halves, and so

is the list with the largest item removed. For a number, smaller might mean

one less, or half as much, or one digit shorter. For a grid, it might mean one

fewer row, or one quarter of the area.

FIG 3Four ways to make a sorting problem smaller

	what the smaller problem	the combining step	work done combining	total cost
remove the first item	1	1	1	2
remove the smallest item	1	1	1	2
split into halves	1	1	1	1
remove a random item	1	1	1	1

Every row is a valid way to make the problem smaller and they do not cost the same. The first two insert one item into a sorted result, which costs a pass each time and gives the slow sorts. The marked rows do less combining work and give the fast ones. A one in a column means only that the row has such a step; the point of the table is the final column, where a two means the cost grows with the square and a one means it grows gently.

The test for a good choice is whether the combining step can be written at

all, and whether it is genuinely cheaper than the original problem. Two

failures are common.

The first is a smaller problem whose answer does not help. Knowing the sorted

order of a list tells you nothing directly about whether it contains two items

that add to a hundred, so sorting as the smaller problem is a dead end for

that question unless the combining step does real work.

The second is a combining step that has to look at the whole input again. If

assembling the answer requires another full pass over everything, the problem

was not made smaller in any useful sense, and the method will cost as much as

doing it all directly.

The step that does the work

Once smaller is chosen, the combining step is where all the thinking goes, and

it is useful to write it as a sentence before writing it as code.

For counting the items in a list: the count is one more than the count of the

rest. For reversing: the reverse is the reverse of the rest, with the first

item put on the end. For the largest value: the largest is whichever is bigger

out of the first item and the largest of the rest. For the number of ways to

climb a staircase taking one or two steps at a time: the number of ways is the

ways from one step down plus the ways from two steps down, because the last

move was either a single or a double.

FIG 4One problem, the sentence, and the step

step	problem	smaller case	the sentence	the step
1	add up a list	the list without its first	the total is the first plus the total of the rest	xs[0] + total(rest)
2	count the items	the list without its first	the count is one more than the count of the rest	1 + count(rest)
3	reverse a list	the list without its first	the reverse is the reverse of the rest, then the first	reverse(rest) + [xs[0]]
4	ways up a staircase	a staircase one or two steps shorter	the last move was a single or a double	ways(n-1) + ways(n-2)
5	is it a palindrome	the word without its two ends	the ends must match and the middle must be one	ends equal and palin(middle)

5 steps

Writing the sentence first is the whole discipline. Every one of these took longer to put into words than to put into code, and the last row has two smaller cases rather than one, which is perfectly allowed and is where lesson five finds its trouble.

Two details in that table matter later. The staircase row calls itself twice,

and the palindrome row shrinks by two rather than by one. Neither is unusual.

A recursion may use any number of smaller answers and may shrink by any

amount, so long as it shrinks.

What this has bought, and what it has not

What has been bought is a way of writing a solution that fits in three lines

and is checkable in a few seconds. That is genuinely valuable, and for many

problems it is the end of the story.

What has not been bought is anything about cost. The methods in this lesson do

not say how much work happens, how much memory is held while the calls are

outstanding, or whether the same small problem is being solved repeatedly. The

staircase row in that last table, written exactly as it reads, is unusable

beyond about forty steps, and nothing in how it was derived gives any hint of

that.

The next three lessons are about what the machine is actually doing while all

this elegance runs, and the three after that are about the repair.

Recap

The method is to assume the smaller version of the problem is already answered, and then write only the step that turns that answer into the full one.
That assumption is not wishful thinking, because the same reasoning applied to the smaller case assumes a smaller one still, and the chain has to end somewhere.
Most of the difficulty is in choosing what smaller means, since the wrong choice produces a step that cannot be written at all.

This 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

NextWhere the Recursion Stops →