From naive recursion to dynamic programming

How does a computer compute F(n)? The direct translation of the definition is recursive:

   fib(n) :
       if n < 2 : return n
       else     : return fib(n-1) + fib(n-2)

Simple, but disastrous. To compute fib(5), the call tree keeps recomputing the same values:

                fib(5)
              /        \
          fib(4)       fib(3)
          /    \        /    \
      fib(3) fib(2)  fib(2) fib(1)
       /   \
   fib(2)  fib(1)

fib(3) is recomputed several times, fib(2) even more. The number of calls swells at roughly the rate of φ per level: the cost is exponential, on the order of φ^n. Computing fib(50) this way already takes billions of calls.

The cure has a name: dynamic programming. Its principle: never compute the same sub-value twice. Two variants:

• Memoization: store every result already obtained, and reuse it.
• Bottom-up iteration: climb from F(0) to F(n), keeping only the last two terms.

   a, b = 0, 1
   repeat n times :  a, b = b, a + b
   return a

Cost: linear — n additions — and constant memory. We go from billions of operations to a few dozen. This is the canonical example of dynamic programming: it shows why "recomputing" is the enemy, and why storing sub-results changes everything.