Fibonacci with DP

Naive recursion computes each value many times over, so the number of calls grows exponentially with the input. Dynamic programming computes each value once: either by caching the results of the recursive calls, or by filling a table from the bottom up.

def fib_memo(n, memo):
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]


def fib_table(n):
    if n < 2:
        return n
    table = [0] * (n + 1)
    table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]


print(fib_memo(40, {}), fib_table(40))

The outputs are both 102334155, which is the fortieth Fibonacci number. The naive version would need over a hundred million calls to produce the same value, while both of these need about forty.

The mechanism is that the Fibonacci recurrence only ever refers to two smaller values, so there are n distinct subproblems rather than exponentially many. Memoisation computes each of them once and caches it; tabulation computes them in increasing order so that every dependency is already in the table when it is needed.

The trade-off to name is that the table version uses O of n space while a two variable version of the same recurrence uses O of 1. That is the general shape of the optimisation here: after you have the recurrence right, look for whether you need to keep the whole history or only the last couple of values. The naive recursive version also has a recursion depth of n, so it fails with a stack error long before it finishes, which is a practical reason to move away from it even when the input is small.

Keep the two most recent values and slide them along. Each new value is the sum of the previous two, so nothing older is ever needed.

def fib(n):
    if n < 2:
        return n
    previous, current = 0, 1
    for _ in range(2, n + 1):
        previous, current = current, previous + current
    return current


print(fib(10))
print(fib(40))

The outputs are 55 and 102334155, the tenth and fortieth Fibonacci numbers.

The mechanism is that the recurrence only depends on the last two values, so the pair of variables acts as a window over the sequence. The simultaneous assignment is important: the right hand side is evaluated before either variable is updated, so both new values are computed from the old pair.

The trade-off to name is that this version uses O of 1 space against the O of n table used by the straightforward bottom up dynamic program. The time is linear in both cases, so the saving is purely in memory. The related trick is fast doubling, which computes the answer in logarithmic time using matrix exponentiation or the identity that the nth Fibonacci number can be expressed in terms of the values at n divided by two, and that is what you would reach for if n were large enough for linear time to matter.