Fibonacci in Java — Naive Recursion, Memoization, Tabulation, O(1) Space

There are four standard implementations plus two advanced ones.

1. Naive recursion

• fib(n) = fib(n-1) + fib(n-2), base case fib(0)=0, fib(1)=1
• Time: O(2^n) — each call branches twice
• Space: O(n) for recursion stack
• fib(40) takes ~30 seconds; fib(50) takes minutes
• Educational only — never in production

Why it's slow: massive recomputation. fib(3) computed many times in fib(10).

2. Memoization (top-down)

• Recursive + cache (array or HashMap)
• Sentinel value (-1) marks 'not computed'
• Each subproblem computed once — O(n) time
• O(n) space (cache + recursion stack)
• Stack overflow at ~10K depth; mitigate with -Xss

3. Tabulation (bottom-up)

• Iterative, fills dp[] array from base to n
• dp[0] = 0; dp[1] = 1; dp[i] = dp[i-1] + dp[i-2]
• O(n) time, O(n) space
• No recursion overhead, no stack risk
• ~10× faster than memoization (constant factor)

4. Space-optimized O(1)

• Only last two values matter — just two variables
• prev2, prev1, curr = prev1 + prev2
• O(n) time, O(1) space
• The gold-standard interview answer

Why O(1) works

• dp[i] depends only on dp[i-1] and dp[i-2]
• No need to remember earlier values
• Generalization: rolling-array technique applies to many DPs

5. Matrix exponentiation

• [[F(n+1), F(n)], [F(n), F(n-1)]] = [[1,1],[1,0]]^n
• Use fast power (square and multiply)
• O(log n) time
• For huge n (10^9 to 10^18) in competitive programming

6. Binet's formula (closed-form)

• fib(n) = (φ^n - ψ^n) / √5
• O(1) time
• Floating-point precision fails beyond fib(70)
• Don't use for accurate large values

Edge cases and overflow

Edge cases

• n = 0 → 0
• n = 1 → 1
• n < 0 → throw or extend with negative-index formula

Overflow

• int overflows at fib(47)
• long overflows at fib(93)
• Use BigInteger for n ≥ 93
• BigInteger arithmetic is O(d) per add (d = digits) — overall O(n^2)

Implementation choice

For interviews

• Lead with O(1) space tabulation
• Mention naive, memoization, tabulation as evolution
• Bonus: matrix exponentiation for log n

For production

• Use O(1) tabulation if you need a few values
• Cache results if called repeatedly with same n
• BigInteger for n > 92

For competitive programming

• O(1) tabulation for normal n
• Matrix exponentiation when n > 10^7
• BigInteger + matrix exponentiation for huge exact values

Concrete benchmark for fib(45)

• Naive: ~30 seconds
• Memoized: ~2 microseconds
• Tabulation: ~250 nanoseconds
• O(1) tabulation: ~250 nanoseconds (same time, less memory)

Common pitfalls

1. Off-by-one in base cases

• Make sure n=0 returns 0, n=1 returns 1

2. Using int and overflowing

• fib(47) > Integer.MAX_VALUE
• Use long up to fib(92), BigInteger beyond

3. Not space-optimizing when possible

• Interviewer expects O(1) space for Fibonacci specifically

4. Stack overflow on recursive solutions

• Default JVM stack ~10K frames
• fib(10000) recursive crashes
• Switch to tabulation

5. Floating-point Binet for large n

• Diverges from true integer beyond fib(70)

Recommendation: For interviews, lead with the O(1)-space tabulation — it demonstrates you understand the dependency structure (only last two values matter) and have applied space optimization. Briefly walk through the evolution: naive (O(2^n) — unusable), memoization (O(n) but recursion overhead), tabulation (O(n), faster), then O(1) space (the optimal). For bonus points, mention matrix exponentiation for O(log n) when n is huge, and note that Binet's closed-form formula has floating-point precision limits beyond fib(70). Always handle overflow correctly — int overflows at fib(47), long at fib(93); use BigInteger for n ≥ 93. The O(1)-space pattern generalizes: for any DP where state i depends only on the last k states (climbing stairs, house robber, certain grid DPs), you can reduce space from O(n) to O(k). For production code, the O(1)-space iterative version is the right default; cache results if the function is called repeatedly with the same n. For competitive programming, switch to matrix exponentiation when n exceeds about 10^7. The mental model: Fibonacci is the canonical DP problem — if you can derive all four versions and explain the trade-offs, you've internalized DP fundamentals: recurrence → memoize → tabulate → space-optimize → advanced (log-n techniques).