Introduction

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13, ...) where F(n) = F(n-1) + F(n-2) is a classic problem for exploring algorithmic optimization. The naive recursive solution has exponential time complexity O(2^n), making it impractical for even moderately large inputs. Several techniques — memoization, bottom-up iteration, matrix exponentiation, and closed-form formulas — dramatically improve performance from exponential down to O(n) or even O(log n).

Method 1: Naive Recursion — O(2^n)

The direct translation of the mathematical definition:

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 ~40 seconds
8# fib_naive(50) is practically impossible

The problem: fib_naive(5) computes fib(3) twice, fib(2) three times, and fib(1) five times. The number of function calls grows exponentially.

Method 2: Memoization (Top-Down DP) — O(n)

Cache previously computed results:

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 — instant
10
11# Manual memoization
12def fib_memo_manual(n, cache={}):
13    if n in cache:
14        return cache[n]
15    if n <= 1:
16        return n
17    cache[n] = fib_memo_manual(n - 1) + fib_memo_manual(n - 2)
18    return cache[n]

Time: O(n). Space: O(n) for the cache and recursion stack.

Method 3: Bottom-Up Iteration — O(n)

Build the sequence from the bottom, using constant 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 — instant

Time: O(n). Space: O(1). This is the most practical solution for most use cases — no recursion stack, no cache overhead.

Method 4: Matrix Exponentiation — O(log n)

The Fibonacci recurrence can be expressed as matrix multiplication:

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

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

1def matrix_mult(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 matrix_pow(M, n):
8    if n == 1:
9        return M
10    if n % 2 == 0:
11        half = matrix_pow(M, n // 2)
12        return matrix_mult(half, half)
13    else:
14        return matrix_mult(M, matrix_pow(M, n - 1))
15
16def fib_matrix(n):
17    if n <= 1:
18        return n
19    result = matrix_pow([[1, 1], [1, 0]], n)
20    return result[0][1]
21
22print(fib_matrix(1000))  # Computes the 1000th Fibonacci number instantly

Time: O(log n) matrix multiplications. Each multiplication involves constant (2x2) matrices, but the numbers themselves grow exponentially, so arithmetic on large numbers adds overhead.

Method 5: Fast Doubling — O(log n)

An optimization of matrix exponentiation using the identities:

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

1def fib_fast_doubling(n):
2    if n < 0:
3        raise ValueError("Negative argument")
4
5    def _fib(n):
6        if n == 0:
7            return (0, 1)
8        a, b = _fib(n // 2)
9        c = a * (2 * b - a)
10        d = a * a + b * b
11        if n % 2 == 0:
12            return (c, d)
13        else:
14            return (d, c + d)
15
16    return _fib(n)[0]
17
18print(fib_fast_doubling(1000000))  # Computes F(1,000,000) in milliseconds

This is the fastest practical algorithm — it avoids matrix multiplication overhead while maintaining O(log n) recursive calls.

Method 6: Binet's Formula (Closed-Form) — O(1)

The golden ratio formula gives F(n) directly:

1import math
2
3def fib_binet(n):
4    phi = (1 + math.sqrt(5)) / 2
5    psi = (1 - math.sqrt(5)) / 2
6    return round((phi**n - psi**n) / math.sqrt(5))
7
8print(fib_binet(10))  # 55
9print(fib_binet(70))  # 190392490709135 — correct
10print(fib_binet(80))  # WRONG — floating point precision fails

Time: O(1). But floating-point precision limits this to approximately n < 75. For larger values, use integer-based methods.

Comparison

Language-Specific Implementations

C++ (Iterative)

1#include <iostream>
2using namespace std;
3
4long long fib(int n) {
5    if (n <= 1) return n;
6    long long a = 0, b = 1;
7    for (int i = 2; i <= n; i++) {
8        long long temp = a + b;
9        a = b;
10        b = temp;
11    }
12    return b;
13}

JavaScript

1function fib(n) {
2    if (n <= 1) return BigInt(n);
3    let [a, b] = [0n, 1n];
4    for (let i = 2; i <= n; i++) {
5        [a, b] = [b, a + b];
6    }
7    return b;
8}
9
10console.log(fib(100).toString());  // Use BigInt for large values

Common Pitfalls

• Recursion depth limit: Python's default recursion limit is 1000. fib_memo(1500) raises RecursionError. Increase with sys.setrecursionlimit(10000) or use iterative/fast-doubling methods.
• Integer overflow: In C/C++/Java, long long overflows at F(92) = 7,540,113,804,746,346,429. Use arbitrary-precision libraries (BigInteger in Java, __int128 in C++) for larger values.
• Floating-point errors in Binet's formula: math.sqrt(5) has limited precision. F(72) computed with Binet's formula is already off by 1. Only use for small n or as an approximation.
• Memoization cache size: @lru_cache(maxsize=None) stores all computed values forever. For very large n, this uses significant memory. Clear with fib_memo.cache_clear() or use iterative methods.
• Off-by-one errors: Some implementations define F(0)=0, F(1)=1 while others define F(1)=1, F(2)=1. Be consistent and document your convention.

Summary

• Use iterative bottom-up (O(n), O(1) space) for most practical applications
• Use fast doubling (O(log n)) for very large Fibonacci numbers (F(1,000,000)+)
• Use @lru_cache memoization for the simplest code with O(n) time
• Avoid naive recursion — it is exponential and unusable beyond n ~ 35
• Avoid Binet's formula for n > 70 due to floating-point precision limits