Answers · Making it fast enough

What's the difference between memoized recursion and filling a DP table bottom-up?

In shortMemoised recursion keeps the calls and only solves states it reaches; a bottom-up table removes the calls, fills every entry in a dependency-safe order, and is usually faster when most entries are needed.

Memoised recursion and a bottom-up table compute the same answers; the difference is where the answers live and who drives the order. Memoised recursion keeps the recursive calls, adds a store, and writes an entry when a call returns. A bottom-up table puts the smallest answers into an array first and fills forward with loops, so there are no waiting calls at all. The first can skip states it never reaches; the second usually computes every entry in its range, and pays for that by being predictable.

W(0)=W(1)=1,\qquad W(i)=W(i-1)+W(i-2)\quad(i\ge 2)

The arithmetic at twenty-five

Take the staircase count $W(n)$ . Without a store, $W(25)$ makes 242,785 calls. To see that, let $C(n)$ be the number of calls made by $W(n)$ . The base cases cost one call each, so $C(0)=C(1)=1$ . Then $C(2)=1+1+1=3$ , $C(3)=1+3+1=5$ , $C(4)=1+5+3=9$ , and in general $C(n)=2F_{n+1}-1$ . Since $F_{26}=121393$ , $C(25)=2\times 121393-1=242785$ . The memoised version computes each of the 24 states 2 through 25 once, and each computation makes two calls, so its call count is $1+2\times 24=49$ . The table version initialises 26 entries to 1 and runs the loop for $i=2,\ldots,25$ : 24 iterations, each one addition and two array reads. All three versions return 121393.

Why it is not just style

The common misreading is that the table is the same recursion with tidier syntax. It is not, because the memoised version still pays for entering and leaving a function and for a key lookup once per state, and it obeys whatever order the recursion happens to take. The table version pays for a loop and array indexing instead. Also, the phrase 'fills only what is needed' belongs to memoisation, not to the table: the table loop writes every index in its range whether the final answer depends on it or not. For $W(25)$ every state is needed, so the two forms fill the same 24 entries; for a sparse recurrence the memoised version can fill a handful while the table fills the whole range.

The order is the test

The only genuinely new obligation is ordering. Entry $i$ reads $i-1$ and $i-2$ , so counting upwards works. In two dimensions, if each cell reads the cell above and the cell to its left, filling rows from top to bottom and each row left to right works. If each cell reads above and right, that row order fails and each row must be filled right to left. If a cell can read a cell on either side of its own row, no order exists: the dependencies have a cycle, and the recursion it came from would not terminate either. The table form exposes that before you run it.

FIG 1

situation	better form	why
most entries in the range are needed	bottom-up table	no call overhead, no nesting, and memory can be reduced
only a small scattered set of states is reached	memoised recursion	a full table would compute entries for nothing
arguments are not simple numbers	memoised recursion	a store can key on anything; a table needs an order
memory is the binding constraint	bottom-up table	rows can be thrown away as they are passed
the formula is still being corrected	memoised recursion	two lines added to a correct recursion, with no reordering to get wrong

The table gives up skipping. It removes depth: at sizes where the plain recursion would nest far beyond the limit, the table is fine because nothing is nested. It also makes memory predictable and reducible. For the staircase, two variables are enough because the formula reaches back only two places. For an 18 by 18 grid, keeping one row instead of the whole table stores 18 entries rather than $18\times 18=324$ , a factor of 18, and $grid\_paths(18,18)$ still returns 2333606220. But throwing the table away throws away the route. If the answer wanted is a number of ways, two variables suffice; if it is a best route or the chosen items, the table has to be walked back, so either keep it or keep enough to rebuild the choices.

Memoised recursion is the safer first form when the recurrence is still being checked, because it adds a store to a correct recursion without changing the order of calls. The bottom-up table is what to use once the recurrence is right and most entries are needed, because it removes the nesting and the call cost and makes the memory visible. Neither is a formatting choice: one keeps a store and a stack, the other keeps an array and an order.

Worth keeping

Memoising a recurrence saves repeated work but leaves the call stack in place; a bottom-up table removes the stack by filling every needed entry in a fixed order.
A bottom-up table is only valid when every entry is written after the entries it reads.
When only a small scattered part of the state space is reachable, memoised recursion can do less work than a full table.

Where this goes next

This question is one step of Answers Built From Smaller Answers, a course that works through its subject from the beginning. The page that teaches this part of it is Working Bottom Up Instead, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course