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.

What Fibonacci Dynamic Programming Actually Eliminates

Fibonacci dynamic programming replaces the naive recursive tree with a linear computation by caching overlapping subproblem results. The core mechanic is simple: store each computed Fibonacci number so that F(n) = F(n-1) + F(n-2) becomes an O(n) lookup and addition instead of an O(2^n) explosion of repeated calls. This is the textbook case of top-down memoization or bottom-up tabulation — both eliminate the exponential waste.

In practice, the bottom-up approach iterates from F(0) and F(1) upward, building an array of size n+1. This gives O(n) time and O(n) space, which can be further reduced to O(1) space by keeping only the last two values. The key property: every subproblem is solved exactly once. For n=46, the 46th Fibonacci number (1836311903) fits in a 32-bit signed integer; at n=47, it overflows to a negative value — a silent corruption that breaks any production system relying on correctness.

Use this technique whenever a problem exhibits optimal substructure and overlapping subproblems — the two hallmarks of dynamic programming. In real systems, Fibonacci is rarely the end goal, but it’s the canonical model for understanding how to transform exponential recursion into linear iteration. Master this pattern, and you can apply it to sequence alignment, pathfinding, and resource allocation where naive recursion would be infeasible.

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);
    }
}

Basic of DP: Why Fibonacci Is the Gateway Drug, Not the Destination

Most tutorials leave you with Fibonacci and act like you've seen the whole DP universe. That's a lie. Fibonacci is the "hello world" of DP — it proves you understand the mechanism, but it doesn't teach you to spot DP problems in the wild.

Real DP is about identifying overlapping subproblems and optimal substructure in problems that don't scream "recurrence relation" at you. The unbounded knapsack, edit distance, and longest increasing subsequence all share the same DNA: they decompose into smaller versions of themselves.

Here's the litmus test: If you can draw a recursion tree where the same node appears more than once, you've got a DP candidate. Fibonacci's tree is a mess of redundant nodes. But so is a shortest-path graph with cycles. So is a sequence alignment with mismatches. The patterns repeat — you just need to learn to see them.

Start with Fibonacci to internalize memoization and tabulation. Then immediately apply that skeleton to climbing stairs, then to 0/1 knapsack. That's when the intuition hardens into instinct.

// io.thecodeforge — dsa tutorial

public class DpDetectorTemplate {

    // Is this a DP candidate? Check for overlapping subproblems.
    // Use this skeleton: recurse, cache, return.
    static int cachedFib(int n, int[] cache) {
        if (n <= 1) return n;
        if (cache[n] != -1) return cache[n];
        cache[n] = cachedFib(n - 1, cache) + cachedFib(n - 2, cache);
        return cache[n];
    }

    public static void main(String[] args) {
        int n = 10;
        int[] cache = new int[n + 1];
        java.util.Arrays.fill(cache, -1);
        System.out.println(cachedFib(n, cache)); // 55
    }
}

Basic Problems: Climbing the Stairs — Fibonacci's Disguised Twin

You've mastered Fibonacci, and now some interviewer hits you with "Count ways to climb N stairs taking 1 or 2 steps." Do you panic? No. Because you recognize it's Fibonacci in a trenchcoat.

Let's prove it: to reach stair N, you either came from stair N-1 (1 step) or stair N-2 (2 steps). So f(N) = f(N-1) + f(N-2). That's literally the Fibonacci recurrence with f(1)=1, f(2)=2. Compute it with tabulation — O(N) time, O(1) space.

But here's where it gets interesting: the moment steps change (1, 2, 3), your recurrence changes. Then weighted stairs add cost per step — that's a shortest-path DP in disguise. The shell is the same; only the recurrence condition mutates.

Master these siblings: climbing stairs, tribonacci numbers, and Lucas numbers. They're the same concept rotated. Rotate it enough times in your head, and you'll spot DP patterns in any recursive mess an interviewer throws at you.

// io.thecodeforge — dsa tutorial

public class ClimbingStairsTabulation {

    static int countWays(int n) {
        if (n <= 1) return 1;
        int prev2 = 1; // f(0)
        int prev1 = 1; // f(1)
        for (int i = 2; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println(countWays(n)); // 8 (ways: 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1)
    }
}

Space Optimization — Slash Memory From O(n) to O(1) Without Breaking a Sweat

You don't need an entire array to compute the nth Fibonacci number. That tabulation table with n+1 slots? Pure waste when you only care about the last two values. Real production code chokes on memory when n hits 10 million — you'll OOM before you blink.

The trick: track only two variables. Each iteration shifts them forward like a conveyor belt. Previous becomes second-previous, current becomes previous, next gets computed fresh. That's it. No cache, no stack frames, no garbage collector headache.

This isn't just a Fibonacci optimization — it's a pattern you'll use in rolling array problems, sliding window DP, and any recurrence that only depends on the last k states. Senior engineers spot these dependencies instantly. The rest allocate memory they don't need.

// io.thecodeforge — dsa tutorial

public class SpaceOptimizedFib {
    public static long fib(int n) {
        if (n <= 1) return n;
        long prev2 = 0, prev1 = 1;
        for (int i = 2; i <= n; i++) {
            long current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }

    public static void main(String[] args) {
        System.out.println(fib(10)); // 55
        System.out.println(fib(50)); // 12586269025
    }
}

Fast Doubling — O(log n) Fibonacci When Linear Isn't Fast Enough

O(n) still sucks when n is 10^12. Spinning a loop a trillion times won't finish before your next sprint planning. Matrix exponentiation works, but fast doubling is cleaner: two formulas that halve the problem size at every step using only multiplication.

F(2k) = F(k) (2F(k+1) - F(k)) F(2k+1) = F(k+1)^2 + F(k)^2

These identities let you skip straight to the answer. You trade addition for multiplication, but the recursion depth drops to O(log n). This is the version used in production-grade math libraries and competitive programming when the constraints laugh at O(n).

Downside: you're now dealing with big integers even for moderate n. Java's BigInteger handles that, but be ready for heap pressure. Also, implement iteratively if the recursion depth scares you — stack overflow at log2(10^12) is ~40 deep, so you're fine.

// io.thecodeforge — dsa tutorial

import java.math.BigInteger;

public class FastDoublingFib {
    // Returns array [F(k), F(k+1)]
    static BigInteger[] fib(int n) {
        if (n == 0) return new BigInteger[]{BigInteger.ZERO, BigInteger.ONE};
        BigInteger[] half = fib(n / 2);
        BigInteger a = half[0], b = half[1];
        BigInteger c = a.multiply(b.multiply(BigInteger.TWO).subtract(a));
        BigInteger d = a.multiply(a).add(b.multiply(b));
        return (n % 2 == 0) ? new BigInteger[]{c, d} : new BigInteger[]{d, c.add(d)};
    }

    public static void main(String[] args) {
        System.out.println(fib(100)[0]); // 354224848179261915075
    }
}