Memoization: Don't Solve the Same Thing Twice

The slow Fibonacci

Fibonacci numbers: each one is the sum of the two before it (0, 1, 1, 2, 3, 5, 8, …). The obvious recursive code is correct but painfully slow, because it solves the same small problems again and again:

public class Main {
    static long calls = 0;

    static long fib(int n) {
        calls++;
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        int[] tests = {10, 20, 30};
        for (int n : tests) {
            calls = 0;
            System.out.println("fib(" + n + ") = " + fib(n) + " took " + calls + " calls");
        }
    }
}

Output

fib(10) = 55 took 177 calls
fib(20) = 6765 took 21891 calls
fib(30) = 832040 took 2692537 calls

The calls grow about 1.6 times for every +1 to n: that is exponential, roughly O(2ⁿ).

Add a memo

A memo is a notebook of answers already worked out. Before solving, look in the notebook. After solving, write the answer down:

public class Main {
    static long[] memo = new long[91];
    static long calls = 0;

    static long fib(int n) {
        calls++;
        if (n < 2) return n;
        if (memo[n] != 0) return memo[n];      // already solved
        memo[n] = fib(n - 1) + fib(n - 2);     // solve once, remember
        return memo[n];
    }

    public static void main(String[] args) {
        System.out.println("fib(30) = " + fib(30) + " took " + calls + " calls");
        calls = 0;
        System.out.println("fib(90) = " + fib(90) + " took " + calls + " calls");
    }
}

Output

fib(30) = 832040 took 59 calls
fib(90) = 2880067194370816120 took 121 calls

Think of it like this: A teacher asks “what's 7 × 8?” five times. The first time you work it out. After that you just remember.

Remember: Memoization turns repeated work into a lookup. It's the first step toward dynamic programming (Module 18).