Fibonacci and dynamic programming
Ask a computer for the 40th Fibonacci number the obvious way and it makes more than 331 million calls. Ask it with a table and it needs 39 additions. The difference is dynamic programming, and the Fibonacci numbers are where almost everyone meets it first.
The problem
The Fibonacci numbers start 0, 1, and every later number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21 and so on. Written as a rule, F(0) = 0, F(1) = 1 and F(n) = F(n − 1) + F(n − 2). The rule is recursive, and turning it straight into a recursive program is easy, but that program turns out to be very slow.
Why recursion repeats itself
To find F(5), the program asks for F(4) and F(3). F(4) asks for F(3) and F(2), so F(3) is worked out twice, F(2) three times and F(1) five times. Drawn as a tree, the calls nearly double at every level, and the total for F(n) is 2·F(n + 1) − 1 calls. The smaller problems overlap: the same ones come back again and again. That is the sign that dynamic programming will help.
Two ways to remember
Memoization keeps the recursion but writes every answer into a table, and each call looks in the table before doing any work. Tabulation fills the table bottom-up: F(0) and F(1) first, then F(2) from them, F(3) from F(2) and F(1), and so on to F(n). Either way each term is worked out once, so F(n) costs n − 1 additions instead of an exponential number of calls.
An example
Bottom-up for F(7): start with 0 and 1. Then 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 and 5 + 8 = 13, so F(7) = 13 after six additions. Plain recursion would make 2·F(8) − 1 = 41 calls for the same answer. Top-down, the first calls go all the way down to F(1) along the left edge of the tree; on the way back up, almost every second call finds its answer already in the table.
Where the name comes from
Richard Bellman named dynamic programming in the early 1950s while working at the RAND Corporation. He later wrote that he chose programming in the old sense of planning, and dynamic because it sounded impressive and was hard to object to. The method itself, solving a problem through the answers to smaller versions of it, now runs in spell checkers, route planners and DNA comparison.
Explore it
Open the app and press Step. Bottom-up, the orange cell is being filled and the two blue cells are the terms it adds. Switch to top-down and watch the stack of calls under the table grow to n, then shrink as the answers come back; the hint under Additions counts how many calls were answered straight from the table.
Frequently asked questions
What are overlapping subproblems?
Smaller problems that a solution needs more than once. F(n) and F(n − 1) both need F(n − 2), so plain recursion works it out twice, and the waste multiplies further down. Dynamic programming solves each one once and remembers the answer.
Is memoization faster than tabulation?
They do the same additions. Tabulation is usually a little faster because it makes no calls, and it cannot run out of stack space; memoization is handy when only some of the smaller answers are needed, because it works out only those.
Can Fibonacci numbers be computed even faster?
Yes. Using F(2k) = F(k)·(2·F(k + 1) − F(k)) and F(2k + 1) = F(k)² + F(k + 1)², the fast doubling method needs only about log₂ n steps. Binet's formula with the golden ratio gives the same numbers, but rounding errors make it unreliable for large n.
How much memory does the table need?
A full table holds n + 1 numbers, but each new term only needs the two before it, so a loop that keeps two numbers does the same job in constant memory. Keeping the whole table is useful when you want all the terms, or to see how the method works.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Try Fibonacci with dynamic programming