Top-Down With Memoisation, Bottom-Up With a Table

A recurrence can be computed in two ways: top-down, as a recursive function that stores each answer the first time it computes it, or bottom-up, as a loop that fills a table from the base cases upwards. This card shows that the two compute the same entries at the same cost, and what does differ: the order of the work and the call stack it needs.

Memoisation is the top-down form. The function is the recurrence written as recursion, with a memo, a dictionary or array of answers already computed, checked on entry and filled on return. Tabulation is the bottom-up form. A loop fills the table in an order that guarantees every entry the recurrence reads is already there.

A run computed the stall takings 3, 2, 7 and 10 from Define a State and a Recurrence, Then Check Them by Hand both ways, and printed each step.

Both stored the same four values and returned 13. Each entry was computed once, in O(1), so both take O(n) time and O(n) space for the answers. The top-down form starts at the answer and recurses down until it reaches base cases, so it stores the entries in the order the recursion finishes them, best(1) before best(0). The bottom-up form starts at the base cases. The top-down run also reached step 8, where best(3) asked for best(1) a second time and read it from the memo instead of recomputing it.

The difference that matters in practice is the stack. The top-down run was three calls deep at its deepest, and on n stalls it is about n deep, which a long input can overflow; Memoisation vs Tabulation shows the depth at which each language gives up. The bottom-up loop never nests at all.

The top-down form has one advantage: it computes only the entries the answer needs. For fewest coins making 30 from coins of 10 and 25, the run's memoised version reached 5 amounts, 0, 5, 10, 20 and 30, where a table over every amount fills 31. When most states are never reached, memoisation does less work.

Use whichever is clearer for the problem, since the recurrence and the cost are the same. Write the recursion first when the recurrence is new, because it reads like the recurrence; turn it into a loop when the input is deep or memory must shrink.