Answers Built From Smaller Answers
Working Bottom Up Instead
Last timeWriting Each Answer Down Once
Turn 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.
The same thing, written the other way round
The remembered recursion from the previous lesson works by going down to the
smallest case and filling the store on the way back up. Every answer in the
store was written in order from the smallest to the largest, because that is
the order the calls finished in.
If that is the order they end up in, the recursion can be skipped and they can
be written in that order directly.
def ways_plain(n):
if n <= 1:
return 1
return ways_plain(n - 1) + ways_plain(n - 2)
def ways_kept(n, seen={}):
if n <= 1:
return 1
if n not in seen:
seen[n] = ways_kept(n - 1, seen) + ways_kept(n - 2, seen)
return seen[n]
def ways_table(n):
table = [1] * (n + 1) # the two smallest cases are both one
for i in range(2, n + 1):
table[i] = table[i - 1] + table[i - 2] # the call became a lookup
return table[n]
print(ways_plain(25), ways_kept(25), ways_table(25)) # all 121393
print(ways_table(200000)) # fine, and nothing is nestedThe translation is mechanical. Wherever the recursion called itself, the table
version reads an entry already written. Wherever the recursion answered a
smallest case outright, the table version puts that value in before the loop
starts. The formula in the middle is unchanged.
Getting the order right
The one genuinely new thing is the order of filling. Every entry must be
written after everything it refers to.
For the staircase this is obvious, since entry reads entries and
, so counting upwards works. For a table with two coordinates it needs
a moment's thought. If each cell reads the cell above it and the cell to its
left, then filling row by row from the top, left to right within each row,
works. If a cell reads the cell to its right, filling left to right does not
work and the rows have to be filled the other way.
The lesson stops here
5 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