Fibonacci

Category: Dynamic Programming

The problem

fib(n) = fib(n-1) + fib(n-2) is a one-line definition — and translated literally into recursive code, it's a trap. Computing fib(n-1) and fib(n-2) both eventually need fib(n-2), fib(n-3), and so on, all the way down — and the naive recursion recomputes every one of those shared subproblems from scratch, every single time it's needed. The number of redundant calls grows exponentially with n.

The solution

Notice that fib(k) only ever has one possible value for a given k — solve it once, and reuse that answer everywhere it's needed instead of recomputing it. Memoization does this top-down: keep a cache, and before recursing, check whether this n has already been solved. Tabulation does the same thing bottom-up: build up fib(0), fib(1), fib(2), ..., fib(n) in a simple loop, so nothing is ever computed before its dependencies exist. Both collapse the cost from exponential to O(n) — memoization by refusing to redo work, tabulation by never being asked to. Tabulation goes one step further here: since each fib(k) only ever needs the previous two values, there's no need to keep a table (or a memo map, or a recursion stack) at all — two variables are enough.

flowchart TD
    F5["fib(5)"] --> F4a["fib(4)"]
    F5 --> F3a["fib(3)"]
    F4a --> F3b["fib(3)"]
    F4a --> F2a["fib(2)"]
    F3b -.->|"same subproblem as F3a - naive recursion solves it again"| F3a

Classic example

classic/Fibonacci implements all three approaches side by side specifically so the benchmark below can measure the same claim three different ways on the same machine. Uses long and rejects n > 90 to stay inside long's range rather than silently overflowing. FibonacciTest covers known base values, that memoized and tabulated agree with naive across a range of inputs, that both agree with each other at the n=90 overflow boundary, and both the negative-n and overflow-boundary rejection guards.

Applied example: correspondent-bank payment route counting

applied/PaymentRouteCounter counts the distinct routes of exactly k correspondent-bank hops from one account to another through a settlement network — the identical overlapping-subproblems shape as this module's Fibonacci numbers, applied to a real question instead of an abstract one. Without memoization, counting routes through a node that multiple partial paths pass through recomputes that node's entire remaining-hop count from scratch every time it's reached — exponential in the hop budget, for exactly the same reason naive fib(n) is. Memoizing on (current node, hops remaining) collapses that to work proportional to network size × hop budget. PaymentRouteCounterTest covers counting multiple routes to the same destination, the zero-hop boundary (only counts when source equals destination), an unreachable hop count, naive and memoized agreeing on the same network, a cyclic network (proving memoization doesn't infinite-loop on cycles), and the null/negative-argument guards.

Benchmark

./gradlew :dynamic-programming:fibonacci:jmh

Real run on this machine (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork). n stays deliberately small — naive Fibonacci at n=35 already takes tens of milliseconds per call, and anything larger would make this benchmark impractically slow, which is itself part of the point:

At n=35, naive is ~78,289x slower than memoized and ~6,057,544x slower than tabulated — for the exact same answer. Naive's own growth confirms the exponential shape directly: going from n=30 to n=35 (5 more steps) costs ~10.7x more time, closely matching the golden ratio's own per-step growth factor (φ ≈ 1.618, and 1.618^5 ≈ 11.1) — Fibonacci's own closed-form growth rate, showing up directly in the naive algorithm's runtime. Memoized and tabulated, meanwhile, barely move across the same range — both linear, with tabulated's near-zero, unmeasurable growth reflecting that it never pays for a HashMap or a recursion stack at all.

When not to use it

• Naive recursion specifically: never, past trivially small n — the benchmark above is the entire argument. There's no scenario where recomputing the same subproblem exponentially many times is the right engineering choice once memoization or tabulation costs nothing extra to write.
• Need the actual sequence of values, not just fib(n)? Tabulation already produces every intermediate value on the way — keep the full array instead of collapsing to two variables if the whole sequence (not just the last term) is needed.
• Subproblems don't actually overlap for your specific recurrence? Then memoization has nothing to save — it's the overlap, not the recursion itself, that naive recursion wastes.

Test coverage

100% instruction coverage, 100% branch coverage (JaCoCo). Reproduce it yourself:

./gradlew :dynamic-programming:fibonacci:jacocoTestReport

Report at dynamic-programming/fibonacci/build/reports/jacoco/test/html/index.html.

Further reading

• Cormen, Leiserson, Rivest & Stein — Introduction to Algorithms (CLRS), 3rd/4th ed., Chapter 15, "Dynamic Programming" — the formal treatment of overlapping subproblems and optimal substructure this module's benchmark demonstrates empirically.
• Skiena — The Algorithm Design Manual, section on Dynamic Programming — frames memoization as "recursion plus a cache," the exact mental model this module's memoized method implements literally.

Unit tests

package com.algorithms.dynamicprogramming.fibonacci.classic;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class FibonacciTest {

    @Test
    void naiveComputesKnownValues() {
        assertThat(Fibonacci.naive(0)).isZero();
        assertThat(Fibonacci.naive(1)).isEqualTo(1);
        assertThat(Fibonacci.naive(10)).isEqualTo(55);
    }

    @Test
    void memoizedMatchesNaiveForTheSameInputs() {
        for (int n = 0; n <= 20; n++) {
            assertThat(Fibonacci.memoized(n)).isEqualTo(Fibonacci.naive(n));
        }
    }

    @Test
    void tabulatedMatchesNaiveForTheSameInputs() {
        for (int n = 0; n <= 20; n++) {
            assertThat(Fibonacci.tabulated(n)).isEqualTo(Fibonacci.naive(n));
        }
    }

    @Test
    void allThreeAgreeAtTheOverflowBoundary() {
        assertThat(Fibonacci.tabulated(90)).isEqualTo(Fibonacci.memoized(90));
        assertThat(Fibonacci.tabulated(90)).isEqualTo(2880067194370816120L);
    }

    @Test
    void rejectsANegativeN() {
        assertThatThrownBy(() -> Fibonacci.naive(-1)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> Fibonacci.memoized(-1)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> Fibonacci.tabulated(-1)).isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsAnNThatWouldOverflowALong() {
        assertThatThrownBy(() -> Fibonacci.naive(91)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> Fibonacci.memoized(91)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> Fibonacci.tabulated(91)).isInstanceOf(IllegalArgumentException.class);
    }
}

package com.algorithms.dynamicprogramming.fibonacci.applied;

import org.junit.jupiter.api.Test;

import java.util.List;
import java.util.Map;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class PaymentRouteCounterTest {

    private static final Map<String, List<String>> NETWORK = Map.of(
            "A", List.of("B", "C"),
            "B", List.of("D"),
            "C", List.of("D"),
            "D", List.of()
    );

    @Test
    void countsBothTwoHopRoutesFromAToD() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThat(counter.countRoutesMemoized("A", "D", 2)).isEqualTo(2);
    }

    @Test
    void zeroHopsOnlyCountsWhenSourceEqualsDestination() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThat(counter.countRoutesMemoized("A", "A", 0)).isEqualTo(1);
        assertThat(counter.countRoutesMemoized("A", "D", 0)).isZero();
    }

    @Test
    void noRouteExistsForAnUnreachableHopCount() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThat(counter.countRoutesMemoized("A", "D", 5)).isZero();
    }

    @Test
    void naiveAndMemoizedAgreeOnTheSameNetwork() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThat(counter.countRoutesNaive("A", "D", 2))
                .isEqualTo(counter.countRoutesMemoized("A", "D", 2));
    }

    @Test
    void naiveCountsZeroWhenTheHopBudgetLandsOnTheWrongNode() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThat(counter.countRoutesNaive("A", "D", 1)).isZero();
    }

    @Test
    void handlesACycleInTheNetworkWithoutInfiniteRecursion() {
        Map<String, List<String>> cyclic = Map.of(
                "X", List.of("Y"),
                "Y", List.of("X")
        );
        PaymentRouteCounter counter = new PaymentRouteCounter(cyclic);

        assertThat(counter.countRoutesMemoized("X", "X", 4)).isEqualTo(1);
    }

    @Test
    void rejectsANullNetwork() {
        assertThatThrownBy(() -> new PaymentRouteCounter(null)).isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsNullFromOrTo() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThatThrownBy(() -> counter.countRoutesMemoized(null, "D", 1)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> counter.countRoutesMemoized("A", null, 1)).isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsNegativeHops() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThatThrownBy(() -> counter.countRoutesMemoized("A", "D", -1)).isInstanceOf(IllegalArgumentException.class);
    }
}

View full JaCoCo coverage report →