Fibonacci Dynamic Programming - Integer Overflow at n=47

Fibonacci numbers look deceptively simple — 0, 1, 1, 2, 3, 5, 8, 13… — but they hide one of the most important lessons in computer science: redundant computation is the silent killer of performance. Interviewers use Fibonacci precisely because it's a lens that reveals whether you understand why brute-force recursion fails at scale. Google, Meta, and Amazon engineers routinely ask candidates to optimise it, because the thinking you apply here transfers directly to harder DP problems like longest common subsequence, coin change, and edit distance.

The core problem is this: computing the 50th Fibonacci number with plain recursion makes over 2 billion function calls. That's not an exaggeration — the call tree branches like a fracklace, recalculating the same sub-results exponentially. Dynamic Programming (DP) fixes this by storing results the first time they're computed so they're never calculated twice. The difference between O(2^n) and O(n) is the difference between your program taking years versus milliseconds.

By the end of this article you'll be able to explain — out loud, to an interviewer — why naive recursion is slow, implement both DP approaches (memoization and tabulation) from scratch in Java, compare their trade-offs, and avoid the three mistakes that trip up most beginners. No prior DP knowledge is assumed. We'll build everything piece by piece.

Why Naive Recursion Destroys Performance — The Problem We're Solving

Before we fix anything, we need to feel the pain of the broken version. The recursive Fibonacci definition is beautiful on paper: fib(n) = fib(n-1) + fib(n-2). But when you translate that directly into code, something ugly happens under the hood.

Every call to fib(n) spawns two more calls. Those each spawn two more. By the time you want fib(50), the call tree has over two billion nodes — and most of them are duplicates. fib(48) is calculated twice, fib(47) three times, fib(46) five times. The overlap grows exponentially.

Think of it like baking a birthday cake by going to the shop to buy flour every single time you need a cup of it — including mid-bake. You'd make fifty trips. The sensible thing is to buy all the flour at the start and measure from the bag. DP is that bag of flour.

The time complexity of naive recursion is O(2^n). At n=50, that's roughly 1,125,899,906,842,624 operations. Modern laptops do about 10^9 operations per second — so you'd be waiting over two weeks. This is not theoretical; run the code below and watch your terminal freeze at fib(50).

public class NaiveFibonacci {

    /**
     * Naive recursive Fibonacci — correct but catastrophically slow.
     * Time complexity: O(2^n)  — doubles the work for every extra step.
     * Space complexity: O(n)   — call stack depth equals n.
     */
    public static long fib(int n) {
        // Base cases: fib(0) = 0, fib(1) = 1 — the sequence's starting seeds
        if (n == 0) return 0;
        if (n == 1) return 1;

        // Every call spawns TWO more calls — this is where the explosion happens
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        // These small values are fine — the tree is tiny
        System.out.println("fib(5)  = " + fib(5));
        System.out.println("fib(10) = " + fib(10));
        System.out.println("fib(20) = " + fib(20));

        // Count how many times fib(3) is recalculated inside fib(10)
        // (It's called 8 times — wasteful even at n=10)
        System.out.println("\nfib(40) = " + fib(40)); // starts to feel slow
        // DO NOT try fib(60) here — it will run for minutes
        System.out.println("\nNotice fib(40) was slow. Imagine fib(80).");
    }
}

Memoization — The Top-Down DP Approach (With a Notebook Analogy)

Memoization is the first way to apply DP. The word comes from 'memo' — as in, you write a memo to yourself so you don't repeat work. The strategy is top-down: start at the big problem (fib(n)), break it down recursively as before, but this time write down every answer in a notebook (an array or HashMap) the first time you compute it. Next time the same question comes up, just read from the notebook.

Here's the analogy in full: imagine you're a student and your teacher keeps asking you random Fibonacci questions during class. The first time they ask 'what's fib(10)?', you work it out and write '55' next to 'fib(10)' in your notebook. The next time they ask fib(10) — even mid-calculation of fib(12) — you just glance at your notebook. Zero thinking required.

The code change is minimal but the impact is massive. We add a memo array initialised to -1. Before computing, we check: 'have I seen this before?' If yes, return the stored answer. If no, compute, store, then return.

Time complexity drops from O(2^n) to O(n). Space complexity is O(n) for the memo table plus O(n) for the call stack — so O(n) overall. Every unique sub-problem is solved exactly once.

import java.util.Arrays;

public class MemoizedFibonacci {

    /**
     * Top-Down Dynamic Programming — Memoization.
     * We use a memo array as our 'notebook'.
     * Time:  O(n) — each unique fib value computed exactly once.
     * Space: O(n) — memo array + recursive call stack.
     */
    public static long fib(int n, long[] memo) {
        // Base cases — the two seeds every Fibonacci sequence starts from
        if (n == 0) return 0;
        if (n == 1) return 1;

        // CHECK THE NOTEBOOK FIRST — did we already compute this?
        // memo[n] != -1 means we've been here before and stored the answer
        if (memo[n] != -1) {
            return memo[n]; // Return instantly — zero recursion needed
        }

        // First time visiting fib(n) — compute it the normal recursive way...
        long result = fib(n - 1, memo) + fib(n - 2, memo);

        // ...then WRITE IT IN THE NOTEBOOK before returning
        memo[n] = result;

        return result;
    }

    public static void main(String[] args) {
        int target = 50;

        // Create the memo array, sized (target + 1) so index n maps to fib(n)
        // Fill with -1 to mean 'not yet computed'
        long[] memo = new long[target + 1];
        Arrays.fill(memo, -1);

        System.out.println("=== Memoized Fibonacci ===");

        // These will all be instant — even fib(50) completes in microseconds
        for (int i = 0; i <= 10; i++) {
            // Reuse the same memo table — values computed earlier help later calls
            System.out.printf("fib(%2d) = %d%n", i, fib(i, memo));
        }

        System.out.println("...");
        System.out.printf("fib(50) = %d%n", fib(target, memo));
        System.out.println("\nCompleted instantly. Compare that to naive recursion.");
    }
}

Tabulation — The Bottom-Up DP Approach (No Recursion at All)

Memoization is top-down: start big, recurse down. Tabulation is the opposite — bottom-up: start from the smallest known answers and build upward deliberately, filling a table row by row.

Think of it like filling in a multiplication table at school. You don't start at the 12×12 corner and work backwards — you start at 1×1 and fill forward because each cell depends only on cells you've already filled.

For Fibonacci: fib(0) = 0 and fib(1) = 1 are our starting seeds. From there, every subsequent value is just the sum of the previous two entries in our table. We never recurse. No call stack. Just a simple loop.

This is generally preferred in production code for three reasons: no risk of stack overflow for large n, slightly faster in practice due to no function call overhead, and easier to reason about memory usage. The space can even be reduced to O(1) by keeping only the last two values — we'll show that optimisation too.

Time complexity: O(n). Space complexity: O(n) for the full table, or O(1) with the optimised two-variable version.

public class TabulatedFibonacci {

    /**
     * Bottom-Up Dynamic Programming — Tabulation.
     * Build the answer from the ground up using a table.
     * Time:  O(n) — single pass through the loop.
     * Space: O(n) — the fibTable array stores all intermediate results.
     */
    public static long fibTableFull(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        // Create a table where index i will hold the value of fib(i)
        long[] fibTable = new long[n + 1];

        // Seed the table with the two values we know for certain
        fibTable[0] = 0; // fib(0) is defined as 0
        fibTable[1] = 1; // fib(1) is defined as 1

        // Fill every cell from index 2 upward — each depends only on earlier cells
        for (int position = 2; position <= n; position++) {
            // The core DP recurrence: sum the two cells immediately before this one
            fibTable[position] = fibTable[position - 1] + fibTable[position - 2];
        }

        // The answer we want is sitting at the end of the table
        return fibTable[n];
    }

    /**
     * Space-Optimised Tabulation — O(1) space.
     * We only ever need the PREVIOUS TWO values, so we ditch the full table.
     * This is the version you want in memory-constrained environments.
     * Time:  O(n) — same single loop.
     * Space: O(1) — just three variables, no array.
     */
    public static long fibSpaceOptimised(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        long previousPrevious = 0; // Represents fib(i-2)
        long previous         = 1; // Represents fib(i-1)
        long current          = 0; // Will hold fib(i) each iteration

        for (int step = 2; step <= n; step++) {
            current = previous + previousPrevious; // Compute this step's fib value
            previousPrevious = previous;           // Slide the window forward
            previous = current;                    // Slide the window forward
        }

        return current;
    }

    public static void main(String[] args) {
        System.out.println("=== Tabulated Fibonacci (Full Table) ===");
        for (int i = 0; i <= 10; i++) {
            System.out.printf("fib(%2d) = %d%n", i, fibTableFull(i));
        }
        System.out.printf("fib(50) = %d%n%n", fibTableFull(50));

        System.out.println("=== Space-Optimised Fibonacci (O(1) space) ===");
        System.out.printf("fib(50) = %d%n",  fibSpaceOptimised(50));
        System.out.printf("fib(70) = %d%n",  fibSpaceOptimised(70));
        System.out.println("\nSame answers, no array needed — just three variables.");
    }
}

Choosing Between Memoization and Tabulation — When Each Wins

Both approaches give O(n) time. The choice usually comes down to space constraints, stack safety, and how natural the top-down vs bottom-up thinking feels to you.

Memoization wins when: - The recursive solution is almost already written (just add a cache) - You don't need all sub-problems (lazy evaluation — you only compute what's needed) - The problem has irregular dependency patterns (e.g., some branches are pruned)

Tabulation wins when: - You need all sub-problems computed anyway (Fibonacci always does) - n is large (avoiding stack overflow) - Memory is tight (O(1) space optimisation is a big deal) - You want deterministic performance (no recursion overhead)

In an interview, either is acceptable. But being able to articulate the trade-offs — and showing you understand when recursion depth becomes a problem — marks you as a senior engineer.

A concrete heuristic: if you're writing a solution for a coding problem and you already wrote the recursion, memoize it. If you're building a production service where n could be large, use tabulation.

Limitations of Dynamic Programming for Fibonacci — When DP Breaks and What to Do

Dynamic Programming solves Fibonacci efficiently for n up to about 10^6. Beyond that, you hit two walls: integer overflow and time complexity.

Integer overflow: In Java, long maxes out at fib(92). For n > 92, you need BigInteger. BigInteger operations are slower — but still O(n) — and memory grows with the number of digits. That's fine for n up to a few hundred thousand, but beyond that the multiplications (addition in BigInteger is O(number of digits)) cause slowdowns.

Time complexity: O(n) is linear, but at n = 10^9, you have a billion iterations. That's not feasible in real time. The loop itself is fast — about 1 ns per iteration on modern CPUs — but that still gives 1 second for n = 10^6, and 1000 seconds for n = 10^9.

Alternatives for extremely large n: Use matrix exponentiation (O(log n) time) or Binet's formula with floating-point precision. Matrix exponentiation is the standard interview follow-up for "what if n is 10^12?"

Memoization-specific limitation: Stack overflow for recursive depth > ~10,000. Tabulation avoids this.

Concurrency: Both approaches are embarrassingly parallel? Not really — each step depends on the previous two. But you can compute Fibonacci using fast doubling (recursive formula) that splits into independent subproblems. That's beyond the scope of this article but worth noting for senior engineers.

import java.math.BigInteger;

public class FastDoublingFibonacci {

    /**
     * Returns fib(n) using fast doubling method, O(log n).
     * Returns a pair (fib(n), fib(n+1)).
     */
    public static BigInteger[] fib(int n) {
        if (n == 0) return new BigInteger[] { BigInteger.ZERO, BigInteger.ONE };
        BigInteger[] half = fib(n >> 1);
        BigInteger a = half[0];
        BigInteger b = half[1];
        // c = a * (b*2 - a)
        BigInteger c = a.multiply(b.shiftLeft(1).subtract(a));
        // d = a*a + b*b
        BigInteger d = a.multiply(a).add(b.multiply(b));
        if ((n & 1) == 0) {
            return new BigInteger[] { c, d };
        } else {
            return new BigInteger[] { d, c.add(d) };
        }
    }

    public static void main(String[] args) {
        int n = 1000000; // one million
        BigInteger result = fib(n)[0];
        System.out.println("fib(1,000,000) computed via fast doubling");
        System.out.println("Number of digits: " + result.toString().length());
        // Uncomment to print: System.out.println(result);
    }
}