Recomputing
Fibonacci numbers start 0, 1, and each next one is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13. So fib(7) needs fib(6) and fib(5). The arrows show which cells an answer uses.
Plain recursion starts every call from scratch. Working out fib(7) calls fib(5) twice, fib(3) five times and fib(1) thirteen times: 41 calls in all. The tags count how often each one is worked out.
Each step up in n multiplies the calls by about 1.6. So fib(30) makes 2,692,537 calls, yet there are only 31 different questions, fib(0) to fib(30). The same small answers are worked out again and again.
Store answers
Two signs say dynamic programming will help. Overlapping subproblems: the same smaller questions come up many times, like fib(3) here. Optimal substructure: an answer is built from the answers to smaller questions, like the arrows into fib(7).
Memoization keeps the recursive code and adds @cache from functools. The first call for each n stores its answer; a repeat call just reads it back. Every tag drops to ×1, and fib(30) works out only 31 answers.
Tabulation builds the same answers from the bottom up, with a loop and no recursion. Make a list t with one cell per question, then write in the answers you already know: t[0] = 0 and t[1] = 1.
The loop starts at t[2]. It reads the two cells to its left and adds them: t[2] = t[1] + t[0] = 1 + 0 = 1. Both are already filled in, so nothing is worked out twice.
Each pass of the loop fills the next cell from the two before it: 2, 3, 5, 8, 13. Going left to right means every cell a step needs is ready. fib(30) needs only 31 cells and 29 additions.
Coin change
Now a new table: the fewest coins that add up to each amount, with coins worth 1, 3 and 4. Taking the biggest coin first makes 6 as 4 + 1 + 1, 3 coins. The table starts with t[0] = 0.
To make amount a, try each coin c as the last coin: that costs 1 plus the best for a − c, already in the table. Keep the smallest. Filling 1 to 5 gives 1, 2, 1, 1, 2.
t[6] reads three cells: t[5], t[3] and t[2]. The smallest is t[3] = 1, so t[6] = 1 + 1 = 2, made as 3 + 3. The table beats the biggest-coin guess of three coins because it checks every choice.
Both store answers instead of working them out again. Memoization keeps the recursive code and adds a cache. Tabulation fills a table in a set order with a loop, like the last cell here: t[7] = 2, made as 3 + 4.
Try it in Python
;; step 1/12 · Answers built from smaller ones
def fib(n):
if n < 2: return n
return fib(n-1) + fib(n-2)
>>> [fib(n) for n in range(8)]
[0, 1, 1, 2, 3, 5, 8, 13]
Plain recursion calls fib(n) 2 × F(n+1) − 1 times in total (the Leonardo numbers): 41 for fib(7) and 2 × 1,346,269 − 1 = 2,692,537 for fib(30). The ratio between one count and the next tends to the golden ratio, about 1.618. @cache arrived in Python 3.9 and is the same as @lru_cache(maxsize=None). For fib(30), cache_info() reports 31 misses (answers worked out) and 28 hits (answers read back). Memoized recursion still goes one call deeper for each n. CPython stops at about 1000 nested calls by default (sys.getrecursionlimit()), so fib(5000) with @cache raises RecursionError, while the table loop has no such limit.