- Being filled
- Read from
- Answer
Fibonacci with dynamic programming
The Fibonacci numbers are the classic first example of dynamic programming. Plain recursion asks for the same terms again and again, but a table that remembers each term makes the work grow only with n. Choose a term, pick bottom-up or top-down, and step through to see every cell filled once. Press Play to watch the table fill, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. Choose n, the term to work out, and the method: bottom-up fills the table from the left, top-down keeps the recursion but looks in the table first, and the row under the table is then the stack of open calls. New example picks another n. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Type n, the term to work out, and choose Bottom-up or Top-down.
- Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere.
- Watch each cell read the two cells before it. Top-down, the row under the table is the stack of open calls.
Bottom-up and top-down
Bottom-up, also called tabulation, starts with F(0) = 0 and F(1) = 1 and fills the table from left to right: each new cell is the sum of the two cells before it. Top-down, also called memoization, keeps the recursive definition: to find F(n), ask for F(n − 1) and F(n − 2). The difference from plain recursion is that each call first looks in the table, and only works a term out if its cell is still empty. Both fill every cell once and use n − 1 additions.
Why plain recursion is so slow
Without a table, F(n) calls F(n − 1) and F(n − 2), both of those call F(n − 3), and so on: the calls form a tree in which the same terms appear over and over. The number of calls is 2·F(n + 1) − 1, which grows as fast as the Fibonacci numbers themselves: 177 calls for F(10), 21,891 for F(20) and more than 331 million for F(40). Overlapping subproblems like these are exactly what dynamic programming is for.
Frequently asked questions
What is dynamic programming?
A way to solve a problem by splitting it into smaller problems that overlap, solving each smaller problem once, and keeping its answer in a table. The Fibonacci numbers are the simplest example: every term is built from the two before it.
What is the difference between memoization and tabulation?
Memoization keeps the recursive code and stores each answer the first time it is worked out, so later calls just read it. Tabulation fills the table in an order that makes sure every answer a cell needs is already there. Both do the same additions; tabulation avoids the call stack, and memoization only works out the cells that are actually needed.
How many additions does F(n) need?
n − 1 with a table: one for each term from F(2) to F(n). Only the last two terms are ever read, so a program can also keep just two numbers instead of the whole table.
Why does the app stop at n = 40?
F(40) = 102,334,155 still fits easily on the screen, and plain recursion would already need 331,160,281 calls for it. Larger terms grow quickly: F(78) is the largest that a JavaScript number holds exactly.
Is anything sent anywhere?
No. Everything is worked out in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor