Fibonacci, in depth: from exponential recursion to memoization, tabulation and constant-space DP

Definition and indexing

Fix the indexing before writing any code, because half the Fibonacci bugs in interviews and production come from it. With F(0) = 0 and F(1) = 1 the sequence runs 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, so F(10) = 55. Some textbooks start at F(1) = F(2) = 1, which gives the same values shifted by one index, and a counting problem might want F(n + 1) rather than F(n). Write the base cases down as data and test them, rather than trusting memory.

The recurrence says two things. The answer for n depends only on the answers for n - 1 and n - 2, and those are smaller instances of the same problem. That is the shape every DP recurrence has: a state (here just n), a transition (add the two predecessors), and base cases that stop the recursion.

Naive recursion and its call tree

The direct translation is correct and very slow:

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

Count its calls. Let C(n) be the number of calls made to evaluate fib(n). Then C(0) = C(1) = 1 and C(n) = 1 + C(n - 1) + C(n - 2). You can check by induction that C(n) = 2F(n + 1) - 1. The call count grows like the Fibonacci numbers themselves, about 1.618 to the power n, because the golden ratio is the growth rate of the recurrence.

These figures were measured by instrumenting the function, and they match the formula. The last column is the point: fib(30) makes 2.7 million calls to compute only 31 different values. Every other call recomputes something already known. The diagram shows this for fib(5), where fib(3) is evaluated twice and fib(2) three times.

The two properties that make DP work

Dynamic programming applies when a problem has two properties, and Fibonacci shows both plainly. Optimal substructure (for counting problems, simply a correct recurrence) means the answer for a state can be built from answers for smaller states. Overlapping subproblems means the naive recursion asks for the same states many times. Without the second property, as in merge sort where each half is distinct, caching buys nothing and plain divide and conquer is already efficient.

A useful mental picture is the subproblem graph. Draw one node per state and an edge from each state to the states it reads. For Fibonacci that graph has n + 1 nodes and about 2n edges, and it has no cycles. The naive recursion explores every path through this graph, which is exponential. DP visits every node once, which is linear. The running time of any DP is the number of states times the work per transition, here (n + 1) times O(1).

Top-down: memoization

Memoization keeps the recursive shape and adds a cache: before computing a state, look it up, and store each answer on the way out.

def fib_memo(n, memo=None):
    if memo is None:          # never use a mutable default argument directly
        memo = {0: 0, 1: 1}
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cached(n):
    return n if n < 2 else fib_cached(n - 1) + fib_cached(n - 2)

Both versions make O(n) calls and use O(n) memory. The top-down style has real advantages. It is a mechanical change to a correct recursion, and in problems with sparse state spaces it computes only the states the answer needs. Its weakness is the call stack. fib_cached(5000) on a cold cache recurses about 5,000 frames deep, and CPython's default recursion limit is 1000, so it raises RecursionError. Raising the limit with sys.setrecursionlimit moves the problem rather than solving it, because the C stack can still overflow and crash the interpreter. In Java or C++ the equivalent failure is a stack overflow at a depth that depends on frame size and thread stack settings.

A trick that keeps the top-down style is to warm the cache in increasing order, calling fib_cached(i) for i in steps of a few hundred, so no single call recurses deeply. Once you are doing that, though, you have written the bottom-up loop by hand.

Bottom-up: tabulation and constant space

Tabulation fills the table from the base cases upward. The loop order must be a topological order of the subproblem graph, so that every state is computed after the states it reads. For Fibonacci that order is simply increasing n.

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

def fib_two_vars(n):
    a, b = 0, 1               # invariant: a = F(i), b = F(i + 1)
    for _ in range(n):
        a, b = b, a + b
    return a

The table version uses O(n) memory and no recursion. The second version notices that each step reads only the two previous entries, so it keeps a sliding window of two values and uses O(1) memory. Write the loop invariant as a comment, as above. It is what lets a reviewer check the off-by-one behaviour at a glance: after zero iterations a = F(0), and after n iterations a = F(n).

The same reduction works in larger DPs. A 2D table where row i reads only row i - 1 can keep two rows. The price is that you lose the full table, so you can no longer reconstruct which choices produced the answer. When reconstruction matters, keep the table or store compact parent pointers.

Worked example: the trace and two counting problems

Trace fib_two_vars(10). The pairs (a, b) after each iteration are (1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 13), (13, 21), (21, 34), (34, 55), (55, 89), so the function returns 55. Now use the same recurrence on two counting problems.

Climbing stairs. You can climb 1 or 2 steps at a time. How many ways are there to climb n steps? The last move was either a 1-step from n - 1 or a 2-step from n - 2, and those two cases are disjoint, so ways(n) = ways(n - 1) + ways(n - 2) with ways(1) = 1 and ways(2) = 2. The values 1, 2, 3, 5, 8 are F(n + 1). For n = 4 the five ways are 1111, 112, 121, 211 and 22.

Domino tilings. Tile a 2 by n board with 1 by 2 dominoes. The leftmost column is covered either by one vertical domino, leaving a 2 by (n - 1) board, or by two horizontal dominoes, leaving 2 by (n - 2). The count is again F(n + 1). Recognising this shape, where the answer is the sum over a few disjoint ways to make the last move, is the main skill DP practice builds. Change the allowed moves to 1, 2 or 3 steps and the recurrence becomes a three-term sum that the same loop handles with three variables.

How big the numbers get

Fibonacci numbers grow fast enough that the integer type matters almost immediately. F(46) = 1,836,311,903 is the largest that fits in a signed 32-bit integer, and F(47) overflows it. F(92) = 7,540,113,804,746,346,429 is the largest that fits in a signed 64-bit integer, and F(93) overflows. In C, C++ or Java the overflow is silent or undefined behaviour, so a test at n = 93 is worth adding. Python integers grow without limit, but each addition then costs time proportional to the number of digits. F(n) has about 0.694n bits, so the linear loop is really quadratic in bit operations for large n.

Closed forms are tempting and fragile. Binet's formula, F(n) = round(phi^n / sqrt(5)), is exact in double precision only up to F(70). From F(71) on the rounding gives wrong values, as checked against exact integers. Most contest problems ask for F(n) modulo a prime instead, which keeps numbers small. Use integer arithmetic with the modulus applied after every addition, never floating point.

Failure modes

A good test suite for any of these versions compares them against each other for n from 0 to a few hundred, and checks the two overflow boundaries explicitly. The naive version is too slow beyond about n = 30, but it is the best oracle for small n because it is obviously correct.

Trade-offs

The general lesson matters more than Fibonacci itself: start from a correct recurrence, measure the overlap, then pick top-down or bottom-up based on stack depth and on which states are needed. The same progression is worked through on harder problems in Dynamic Programming, in depth, House Robber, in depth and Coin Change, in depth. The O(log n) algebra is in Matrix Exponentiation, in depth.

What to do next

1. Implement all four versions (naive, memo, table, two variables) and cross-check them for n from 0 to 300.
2. Instrument the naive version with a call counter and confirm that calls(20) is 21,891.
3. Run the memoized version at n = 5000 on a cold cache, watch it fail, and explain why the loop does not.
4. Add tests at the overflow boundaries: F(46), F(47), F(92) and F(93) in a 64-bit language.
5. Solve climbing stairs with steps of 1, 2 or 3 using a three-variable rolling window.
6. Then read the fast doubling article and compute F(10^18) mod 1,000,000,007.