Introduction

The naive recursive Fibonacci runs in O(2^n) time because it recomputes the same subproblems. There are several ways to make Fibonacci fast: memoization reduces it to O(n), bottom-up iteration also runs in O(n) with O(1) space, and matrix exponentiation achieves O(log n) time. The fastest practical approach for most use cases is memoization or iteration, while matrix exponentiation is useful for extremely large values of n.

Naive Recursion (O(2^n))

1def fib_naive(n):
2    if n <= 1:
3        return n
4    return fib_naive(n - 1) + fib_naive(n - 2)
5
6print(fib_naive(10))  # 55
7# fib_naive(40) takes several seconds
8# fib_naive(50) takes minutes

Each call branches into two recursive calls, creating an exponential call tree. fib(5) computes fib(3) twice and fib(2) three times.

Memoization (O(n) Time, O(n) Space)

1from functools import lru_cache
2
3@lru_cache(maxsize=None)
4def fib_memo(n):
5    if n <= 1:
6        return n
7    return fib_memo(n - 1) + fib_memo(n - 2)
8
9print(fib_memo(100))  # 354224848179261915075
10# Instant — each value computed once

@lru_cache stores previously computed results. Each fib(k) is calculated exactly once, reducing time from O(2^n) to O(n). A manual dictionary approach works the same way:

1def fib_memo_manual(n, cache={}):
2    if n in cache:
3        return cache[n]
4    if n <= 1:
5        return n
6    cache[n] = fib_memo_manual(n - 1, cache) + fib_memo_manual(n - 2, cache)
7    return cache[n]

Bottom-Up Iteration (O(n) Time, O(1) Space)

1def fib_iterative(n):
2    if n <= 1:
3        return n
4    a, b = 0, 1
5    for _ in range(2, n + 1):
6        a, b = b, a + b
7    return b
8
9print(fib_iterative(100))  # 354224848179261915075

This is the most practical approach for most applications. It uses constant space by only keeping the two most recent values.

1// Java equivalent
2public static long fib(int n) {
3    if (n <= 1) return n;
4    long a = 0, b = 1;
5    for (int i = 2; i <= n; i++) {
6        long temp = a + b;
7        a = b;
8        b = temp;
9    }
10    return b;
11}

Matrix Exponentiation (O(log n))

The Fibonacci recurrence can be expressed as a matrix multiplication:

| F(n+1) |   | 1  1 |^n   | 1 |
| F(n)   | = | 1  0 |   * | 0 |

By using fast matrix exponentiation (repeated squaring), this computes F(n) in O(log n) multiplications:

1import numpy as np
2
3def matrix_power(matrix, n):
4    result = np.identity(len(matrix), dtype=object)
5    base = np.array(matrix, dtype=object)
6    while n > 0:
7        if n % 2 == 1:
8            result = result @ base
9        base = base @ base
10        n //= 2
11    return result
12
13def fib_matrix(n):
14    if n <= 1:
15        return n
16    m = matrix_power([[1, 1], [1, 0]], n)
17    return int(m[0][1])
18
19print(fib_matrix(100))  # 354224848179261915075

Without numpy, a pure Python implementation:

1def multiply_2x2(a, b):
2    return [
3        [a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]],
4        [a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]]
5    ]
6
7def fib_fast(n):
8    if n <= 1:
9        return n
10    result = [[1, 0], [0, 1]]  # Identity matrix
11    base = [[1, 1], [1, 0]]
12    power = n
13    while power > 0:
14        if power % 2 == 1:
15            result = multiply_2x2(result, base)
16        base = multiply_2x2(base, base)
17        power //= 2
18    return result[0][1]
19
20print(fib_fast(1000))  # Computes instantly

Fast Doubling (O(log n), No Matrix)

Fast doubling uses two identities to compute F(n) from F(n/2):

• F(2k) = F(k) * [2*F(k+1) - F(k)]
• F(2k+1) = F(k)^2 + F(k+1)^2

1def fib_doubling(n):
2    if n < 0:
3        raise ValueError("Negative argument")
4
5    def helper(n):
6        if n == 0:
7            return (0, 1)
8        fk, fk1 = helper(n // 2)
9        even = fk * (2 * fk1 - fk)
10        odd = fk * fk + fk1 * fk1
11        if n % 2 == 0:
12            return (even, odd)
13        else:
14            return (odd, even + odd)
15
16    return helper(n)[0]
17
18print(fib_doubling(100))  # 354224848179261915075

Fast doubling has the same O(log n) complexity as matrix exponentiation but avoids matrix overhead and is simpler to implement.

Performance Comparison

Common Pitfalls

• Hitting Python's recursion limit with memoization: Python's default recursion limit is 1000. For fib_memo(5000), you get RecursionError. Either increase the limit with sys.setrecursionlimit() or use the iterative approach for large n.
• Integer overflow in typed languages: In Java or C++, long overflows around F(92). Use BigInteger in Java or unsigned long long in C++ for larger values. Python handles arbitrary-precision integers natively.
• Using mutable default arguments carelessly: The manual memoization pattern def fib(n, cache={}) uses a mutable default that persists across calls, which is the desired behavior here but can cause subtle bugs in other contexts.
• Forgetting that matrix exponentiation has a large constant factor: For small n (under ~1000), the overhead of matrix multiplication makes O(log n) matrix exponentiation slower than simple O(n) iteration. Use matrix methods only when n is very large.
• Confusing fast doubling with divide-and-conquer without memoization: A naive divide-and-conquer that computes fib(n//2) twice per call is still exponential. Fast doubling works because it computes both F(k) and F(k+1) in a single recursive call, halving the problem once per step.

Summary

• Naive recursion is O(2^n) — never use it for n > 30
• Memoization (@lru_cache) or bottom-up iteration bring it to O(n) — best for most use cases
• Matrix exponentiation and fast doubling achieve O(log n) — useful for very large n or competitive programming
• Bottom-up iteration with O(1) space is the most practical general-purpose solution
• Fast doubling is the simplest O(log n) approach, avoiding matrix multiplication overhead