Card 06/ 10
Memoisation vs Tabulation
Write top-down when only some states matter, bottom-up when the input is deep or the space must shrink.
Memoisation and tabulation compute the same recurrence with the same time complexity, so the choice between them turns on everything else: how deep the recursion goes, how many states are needed, and whether the table can shrink. This card compares them on those axes and gives the rule.
Both store one answer per state, both compute each state once, and both take time equal to the number of states times the work per state. A wrong recurrence is wrong in both. The table below compares what differs.
| Aspect | Memoisation, top-down | Tabulation, bottom-up |
|---|---|---|
| How it reads | Like the recurrence, written as recursion | A loop whose order you must work out |
| States computed | Only those the answer reaches | Every state in the table |
| Call stack | As deep as the longest chain of states | None beyond the loop |
| Overhead per state | A function call and a memo lookup | An array read |
| Shrinking the space | Hard, since any stored state may be asked for again | Easy when each entry reads a fixed few before it |
The call stack decides most real choices. A run gave the stall problem a million stalls and tried each form in each language.
| Language | Memoised | Tabulated |
|---|---|---|
| Python 3.14 | RecursionError: maximum recursion depth exceeded, at the default limit of 1,000 | 3,090,906 |
| Java 25 | StackOverflowError | 3,090,906 |
| TypeScript on Node 24 | RangeError: Maximum call stack size exceeded | 3,090,906 |
Every memoised version failed and every tabulated one finished with the same answer. Python stops at its own counter, which sys.setrecursionlimit can raise, but raising it far enough to reach a million risks crashing the interpreter when the real stack runs out. Java and Node stop when the thread's stack is full, and the depth at which that happens depends on the stack size and on how large each call's frame is.
The rule: write memoisation when only a fraction of the states will be reached, as with fewest coins from large coin values, or when the recurrence is new and you want code that reads like it. Write tabulation when the chain of states can be long, roughly beyond a few thousand, or when you want to cut the space, as Keeping Only the Entries the Recurrence Reads does. When in doubt, check the recurrence with memoisation on small inputs and ship the table.
← → move through sections and cards