Fibonacci tabulation: the idea
Prerequisites: Arrays, addition, and a recurrence.
A recurrence defines a value using smaller values. Fibonacci numbers begin F(0) = 0 and F(1) = 1; every later term is F(i−1) + F(i−2). Tabulation fills an array from smaller indices to larger ones, computing each term once. This illustrates dynamic programming: choose subproblems, record their answers, and reuse those answers instead of repeatedly recomputing them.
Try it
Use n = 12 and watch each cell depend on the preceding two. Try n = 0 and n = 1 to see why base cases come first. Compare this table mentally with naïve recursive calls that repeatedly revisit the same indices.
Reading the display
Gray dots are uncomputed entries, cyan cells are completed subproblems, amber cells are dependencies, and pink marks the newly written answer. The final requested term is green.
Time and memory
O(n) additions and O(n) stored values under unit-cost arithmetic. This bounded demo uses exact Number integers through n = 30. A rolling two-value version needs O(1) working space.
The bounds above describe core work on prepared input. String conversion to code-point arrays and editor validation are additional work. The visualization saves the data at each operation so you can step backward. This recording requires extra time and memory beyond the algorithm’s own working storage. Input limits keep the demonstrations manageable.
When to use it—and what to watch
A complete table is useful when multiple earlier terms will be queried. If only the last term is required, retaining every earlier result is unnecessary. Tabulation is one implementation of the recurrence, not a new definition of Fibonacci numbers.
Continue exploring
- 0/1 knapsack — Build a table of best choices under a weight limit.