Fibonacci & Dynamic Programming

Intuition

The Fibonacci numbers are defined by a rule that refers to itself: fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1. Writing that rule directly as a recursive function is the most natural thing in the world — and it is also a trap. The plain recursion recomputes the same subproblems over and over, and the amount of wasted work explodes exponentially. Dynamic programming is the fix: solve each subproblem once, remember the answer, and reuse it. This lesson shows the same computation three ways so you can watch the waste appear and then disappear.

How It Works

Naive recursion (the default view) builds a recursion tree. fib(6) calls fib(5) and fib(4); each of those splits again, all the way down to the base cases fib(1) and fib(0). Because nothing is remembered, an entire subtree like fib(4) is rebuilt from scratch every time it is asked for. The tree's leaves are all 0s and 1s, and the answer is just how many 1-leaves there are — which is exactly why the work grows like the Fibonacci numbers themselves.

Top-down memoization keeps the same recursion but adds a cache. The first time a value like fib(4) is computed, it is stored in memo. Every later request for fib(4) is an O(1) lookup — a cache hit — so that whole subtree is never re-expanded. The tree gets pruned to a thin spine, and the call count collapses from exponential to linear.

Bottom-up tabulation drops recursion entirely. It fills a 1-D table dp[] left to right: dp[0] = 0, dp[1] = 1, then each dp[i] = dp[i-1] + dp[i-2]. Every cell is written exactly once, reading only the two cells just before it. Same answer, no call stack, and you can see the sequence build up in order.

The shared invariant across all three: once fib(k) is known, it never needs to be computed again. The only question is whether you exploit that fact.

Step By Step

Walking the default input — naive mode, n = 6 (so the target is fib(6) = 8):

  1. Call fib(6). It needs fib(5) + fib(4), so it recurses into fib(5) first.
  2. Drill down the left spine — fib(5) → fib(4) → fib(3) → fib(2) — until it bottoms out at the base cases fib(1) = 1 and fib(0) = 0.
  3. Combine upward. With both children resolved, fib(2) = 1 + 0 = 1, then fib(3) = fib(2) + fib(1) = 1 + 1 = 2, then fib(4) = 2 + 1 = 3, then fib(5) = 3 + 2 = 5. Each combine beat does the addition; the following return beat commits the value (green chip) and hands it to the caller.
  4. Recompute fib(4) again. Back at the root, fib(6) still needs its second child fib(4) — and naive recursion has no memory, so it rebuilds that entire subtree from scratch. This is the wasted work the tree makes visible.
  5. Finish. fib(6) = fib(5) + fib(4) = 5 + 3 = 8, after 25 total calls.

Switch to memoization and the same fib(6) resolves in only 11 calls — the second fib(4), fib(3), and fib(2) requests become teal cache-hit stubs. Switch to bottom-up and you watch dp fill 0, 1, 1, 2, 3, 5, 8 directly.

Complexity

ApproachTimeSpaceNotes
Naive recursionO(φⁿ) ≈ O(2ⁿ)O(n) stackRecomputes subproblems; fib(6) = 25 calls
Top-down memoO(n)O(n) memo + stackEach subproblem solved once, then cached
Bottom-up tableO(n)O(n) tableNo recursion; O(1) space if you keep only two cells

The leap from O(2ⁿ) to O(n) is the entire point of dynamic programming: it is the difference between fib(50) finishing instantly and never finishing at all.

Edge Cases

  • n = 0 or n = 1 are base cases — they return immediately with no recursion (this lesson's slider starts at n = 2, the smallest case with a real recurrence).
  • n = 2 is the smallest interesting input: one addition, fib(2) = 1.
  • Mutable default argument (memo={} in Python) is shared across calls — fine here, but a classic footgun in other contexts.
  • Large n overflows fixed-width integers in many languages well before the recursion itself becomes the bottleneck.

Common Mistakes

  • Shipping the naive version. It looks correct and passes small tests, then times out the moment n grows — because the cost is exponential, not linear.
  • Forgetting the base cases, or checking the cache before the base case, so fib(0)/fib(1) get stored or looked up needlessly.
  • Off-by-one in the table. dp must have length n + 1 and you must set both dp[0] and dp[1] before the loop, or the first iteration reads an empty cell.
  • Believing memoization changes the answer. All three approaches return the exact same fib(n); DP only changes how much work it takes to get there.