Computing Fibonacci Numbers

The Fibonacci sequence illustrates the leap from exponential naive recursion to linear dynamic programming and logarithmic matrix methods.

A recurrence with a lesson

The Fibonacci numbers are defined by F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2). Simple as it is, computing them is the classic teaching example for how algorithm design changes running time by orders of magnitude while the answer stays the same.

Naive recursion is exponential

Translating the recurrence directly into recursion makes two calls per level, and the same subproblems are recomputed over and over. The number of calls itself grows like Fibonacci, so the naive method costs O(phi^n), roughly O(1.618^n) time. This is the poster child for overlapping subproblems.

Memoization and tabulation

Memoizing the recursion computes each F(n) once, giving O(n) time. Bottom-up tabulation does the same iteratively, and since each value needs only the previous two, it runs in O(n) time and O(1) space by keeping just two running values.

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a  # O(n) time, O(1) space

Logarithmic time by matrix power

Fibonacci can be computed even faster. The matrix [[1,1],[1,0]] raised to the n-th power has F(n) in its corner, and exponentiation by repeated squaring computes that power in O(log n) matrix multiplications. A closed-form using the golden ratio also exists but suffers floating-point error for large n, so the matrix method is preferred for exact results.

The general lesson

Fibonacci is a stand-in for any problem defined by a recurrence with overlapping subproblems. The same progression, from naive recursion to memoized recursion to bottom-up tabulation to a clever closed or logarithmic method, recurs throughout algorithm design. Recognising overlapping subproblems is the trigger to stop recomputing and start storing, which is the whole message of dynamic programming.