Skip to content

Fibonacci and the DP idea

Each Fibonacci number is the sum of the two before it. Computing it straight from that rule takes exponential time; remembering answers makes it linear. This is dynamic programming in its simplest form.

Naive recursion With memory (DP) Two variables Fast doubling
\(O(\varphi^n)\) calls \(O(n)\) time, \(O(n)\) space \(O(n)\) time, \(O(1)\) space \(O(\log n)\) multiplications

The idea

The Fibonacci numbers are \(F(0) = 0\), \(F(1) = 1\) and \(F(n) = F(n-1) + F(n-2)\): 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Turned directly into a recursive function, \(F(5)\) calls \(F(4)\) and \(F(3)\); \(F(4)\) calls \(F(3)\) again and \(F(2)\); and so on. The same small values are worked out over and over: \(F(20)\) makes 21,891 calls to find 6,765.

The fix is to remember each value the first time it is found. Then each \(F(i)\) is computed once, and \(F(n)\) needs only \(n - 1\) additions. That is the whole idea of dynamic programming: a recursion with overlapping subproblems, plus a memory.

How it works

Three ways, from the slowest to the leanest:

  1. Naive: fib(n) = fib(n-1) + fib(n-2), no memory.
  2. Memoization (top-down): the same function, but first look the answer up in a table; store it before returning. In Python, @lru_cache does this for you.
  3. Tabulation (bottom-up): fill f[0..n] in a loop. Each step needs only the last two values, so two variables are enough.

Code

from functools import lru_cache

calls = 0


def fib_naive(n):
    """Straight from the definition: exponential time, because the same values are worked out again and again."""
    global calls
    calls += 1
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)


@lru_cache(maxsize=None)
def fib_memo(n):
    """Top-down: the same recursion, but each answer is remembered the first time (memoization)."""
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)


def fib_table(n):
    """Bottom-up: fill a table from the smallest case upwards (tabulation)."""
    f = [0] * (n + 1)
    if n > 0:
        f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]


def fib_two(n):
    """Bottom-up with only the last two values kept: O(1) memory."""
    a, b = 0, 1                              # F(i), F(i+1)
    for _ in range(n):
        a, b = b, a + b
    return a


if __name__ == "__main__":
    print(fib_naive(20), calls)
    print(fib_memo(50), fib_table(50), fib_two(50))
    print([fib_two(i) for i in range(11)])

import java.util.ArrayList;
import java.util.List;

public class Fibonacci {
    static long calls = 0;

    /** Straight from the definition: exponential time, because the same values are worked out again and again. */
    static long fibNaive(int n) {
        calls++;
        return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2);
    }

    static long[] memo = new long[100];

    /** Top-down: the same recursion, but each answer is remembered the first time (memoization). */
    static long fibMemo(int n) {
        if (n < 2) return n;
        if (memo[n] != 0) return memo[n];
        return memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
    }

    /** Bottom-up: fill a table from the smallest case upwards (tabulation). */
    static long fibTable(int n) {
        long[] f = new long[n + 1];
        if (n > 0) f[1] = 1;
        for (int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
        return f[n];
    }

    /** Bottom-up with only the last two values kept: O(1) memory. */
    static long fibTwo(int n) {
        long a = 0, b = 1;                            // F(i), F(i+1)
        for (int i = 0; i < n; i++) { long t = a + b; a = b; b = t; }
        return a;
    }

    public static void main(String[] args) {
        long f20 = fibNaive(20);
        System.out.println(f20 + " " + calls);
        System.out.println(fibMemo(50) + " " + fibTable(50) + " " + fibTwo(50));
        List<Long> first = new ArrayList<>();
        for (int i = 0; i <= 10; i++) first.add(fibTwo(i));
        System.out.println(first);
    }
}

#include <iostream>
#include <vector>
using namespace std;

long long calls = 0;

// Straight from the definition: exponential time, because the same values are worked out again and again.
long long fibNaive(int n) {
    calls++;
    return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2);
}

vector<long long> memo(100, 0);

// Top-down: the same recursion, but each answer is remembered the first time (memoization).
long long fibMemo(int n) {
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
}

// Bottom-up: fill a table from the smallest case upwards (tabulation).
long long fibTable(int n) {
    vector<long long> f(n + 1, 0);
    if (n > 0) f[1] = 1;
    for (int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
    return f[n];
}

// Bottom-up with only the last two values kept: O(1) memory.
long long fibTwo(int n) {
    long long a = 0, b = 1;                          // F(i), F(i+1)
    for (int i = 0; i < n; i++) { long long t = a + b; a = b; b = t; }
    return a;
}

int main() {
    long long f20 = fibNaive(20);
    cout << f20 << " " << calls << "\n";
    cout << fibMemo(50) << " " << fibTable(50) << " " << fibTwo(50) << "\n";
    cout << "[";
    for (int i = 0; i <= 10; i++) cout << (i ? ", " : "") << fibTwo(i);
    cout << "]\n";
}

Output: 6765 21891 (the naive version made 21,891 calls for \(F(20)\)), then 12586269025 three times for \(F(50)\), which the naive version would need about 40 billion calls to reach, then the first eleven values.

When to use it

  • The pattern, not the numbers: Fibonacci itself is rarely needed, but the same shape appears everywhere: counting ways to climb stairs taking 1 or 2 steps, tilings of a \(2 \times n\) strip with dominoes, and many "how many ways" questions.
  • Whenever a recursion calls itself on the same arguments more than once, add a memory.

Common mistakes

  • Overflow: \(F(47)\) no longer fits in a 32-bit signed integer and \(F(93)\) overflows 64 bits. The code uses 64-bit long; Python's integers never overflow.
  • Memoizing with a mutable default argument or a global that is never cleared between tests.
  • Recursion depth: top-down memoization still recurses \(n\) levels deep; for large \(n\) use the loop.

Going deeper

Each part below starts closed; open the ones you want.

Sample walkthrough: the call tree of F(5)

Without memory:

F(5)
├── F(4)
│   ├── F(3)
│   │   ├── F(2) ── F(1), F(0)
│   │   └── F(1)
│   └── F(2) ── F(1), F(0)
└── F(3)
    ├── F(2) ── F(1), F(0)
    └── F(1)

That is 15 calls; \(F(3)\) is computed twice and \(F(2)\) three times. With memory, the second \(F(3)\) and the later \(F(2)\)s are looked up, and only 9 calls happen (one per value \(F(0)..F(5)\), plus the look-ups).

Bottom-up for \(F(10)\):

\(i\) 0 1 2 3 4 5 6 7 8 9 10
\(F(i)\) 0 1 1 2 3 5 8 13 21 34 55
The math: how slow is the naive version, and a formula

Counting calls. Let \(C(n)\) be the number of calls made by fib_naive(n). Then \(C(0) = C(1) = 1\) and \(C(n) = 1 + C(n-1) + C(n-2)\). Adding 1 to both sides gives \(C(n) + 1 = (C(n-1) + 1) + (C(n-2) + 1)\), the Fibonacci rule again, so

\[C(n) = 2F(n+1) - 1.\]

For \(n = 20\): \(2 \cdot 10946 - 1 = 21891\), exactly what the program counted.

Binet's formula. With \(\varphi = \frac{1 + \sqrt 5}{2} \approx 1.618\) (the golden ratio) and \(\psi = \frac{1 - \sqrt 5}{2}\),

\[F(n) = \frac{\varphi^n - \psi^n}{\sqrt 5}.\]

Since \(|\psi| < 1\), \(F(n)\) is the whole number nearest to \(\varphi^n / \sqrt 5\). So the naive recursion makes about \(\frac{2\varphi}{\sqrt 5}\varphi^{n} \approx 1.45 \cdot 1.618^n\) calls: exponential.

Matrix form.

\[\begin{pmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n\]

With fast exponentiation this needs only \(O(\log n)\) matrix multiplications. The "fast doubling" identities \(F(2k) = F(k)\,(2F(k+1) - F(k))\) and \(F(2k+1) = F(k)^2 + F(k+1)^2\) do the same with less work.

Watch it step by step

Orange cells are read, red is the cell being filled, green cells are finished.

Variations and related ideas
  • Climbing stairs: the number of ways to climb \(n\) steps taking 1 or 2 at a time is \(F(n+1)\).
  • Tribonacci and other "sum of the last \(k\)" sequences: keep the last \(k\) values.
  • Fibonacci modulo \(m\) repeats with a period (the Pisano period), at most \(6m\).
  • Fibonacci heaps and Fibonacci search borrow the name because Fibonacci numbers appear in their analysis.

See also

References

  • R. Bellman, Dynamic Programming, Princeton University Press, 1957.
  • D. E. Knuth, The Art of Computer Programming, Vol. 1, 3rd ed., Section 1.2.8 (Fibonacci numbers).
  • T. H. Cormen et al., Introduction to Algorithms, 4th ed., Chapter 14 (dynamic programming).