Definition
- Fibonacci sequence –
fib(0) = 0,fib(1) = 1,fib(n) = fib(n-1) + fib(n-2). - Naive recursion – O(2^n) because identical subproblems are recomputed exponentially.
- Memoization – top-down caching reduces to O(n) time and O(n) space.
- Tabulation – bottom-up array filling in O(n) time and O(n) space.
- Rolling – two variables give O(n) time and O(1) space.
- Overflow – fib(93) exceeds
long; use BigInteger for large n.
The National Bank of India projects a reward-points balance where each month's points equal the sum of the previous two months. Instead of recomputing the whole history every time a customer queries their projection, the system remembers the last two months and rolls forward, computing the answer in one pass.
Understanding the Concepts
What is the Fibonacci number problem?
The Fibonacci sequence starts with 0 and 1, and each subsequent number is the sum of the two preceding numbers. The problem asks you to compute the nth Fibonacci number efficiently.
This is the classic introduction to dynamic programming. The naive recursive solution is correct but exponentially slow, and fixing it demonstrates the core DP principle: solve each subproblem once.
package com.bank.dsa;
public class FibIntro {
// Naive: exponential
public static long fibNaive(int n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
// Memoized: linear time, linear space
public static long fibMemo(int n, long[] cache) {
if (n <= 1) return n;
if (cache[n] != -1) return cache[n];
return cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
}
// Rolling: linear time, constant space
public static long fibRolling(int n) {
if (n <= 1) return n;
long prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
long cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
public static void main(String[] args) {
long[] cache = new long[51];
java.util.Arrays.fill(cache, -1);
System.out.println("Naive fib(10) = " + fibNaive(10));
System.out.println("Memo fib(50) = " + fibMemo(50, cache));
System.out.println("Rolling fib(50) = " + fibRolling(50));
}
}
Naive fib(10) = 55
Memo fib(50) = 12586269025
Rolling fib(50) = 12586269025
Why is naive recursion exponentially slow?
The naive recursion creates a binary call tree. Each call makes two further calls, and many subproblems are computed multiple times. Computing fib(5) calls fib(3) twice and fib(2) three times. The total work is approximately O(2^n), growing by the golden ratio (~1.618) at each level.
Computing fib(40) takes over a billion calls, and fib(50) takes minutes on modern hardware. This exponential growth makes the naive version impractical for any input beyond about 40.
package com.bank.dsa;
public class FibCallCount {
private static long calls = 0;
public static long fib(int n) {
calls++;
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
calls = 0;
fib(30);
System.out.println("fib(30) calls: " + calls);
calls = 0;
fib(40);
System.out.println("fib(40) calls: " + calls);
}
}
fib(30) calls: 2692537
fib(40) calls: 331160281
How does memoization fix the problem?
Memoization stores each computed value the first time it is calculated and returns the cached result on subsequent calls. The check-and-cache pattern ensures each unique subproblem is solved exactly once, collapsing the exponential call tree to a linear chain.
package com.bank.dsa;
import java.util.HashMap;
import java.util.Map;
public class FibMemoMap {
private static final Map<Integer, Long> memo = new HashMap<>();
public static long fib(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
long result = fib(n - 1) + fib(n - 2);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
System.out.println("fib(50) = " + fib(50));
System.out.println("Cache size: " + memo.size());
}
}
fib(50) = 12586269025
Cache size: 49
How does the bottom-up rolling approach work?
The bottom-up approach starts from the base cases and iterates forward. Since each value depends only on the previous two, we keep just two variables and slide the window.
package com.bank.dsa;
public class FibRolling {
public static long fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
long twoBack = 0, oneBack = 1;
for (int i = 2; i <= n; i++) {
long current = oneBack + twoBack;
twoBack = oneBack;
oneBack = current;
}
return oneBack;
}
public static void main(String[] args) {
System.out.println("fib(10) = " + fib(10));
System.out.println("fib(92) = " + fib(92));
}
}
fib(10) = 55
fib(92) = 7540113804746346429
How is memoization different from tabulation?
| Aspect | Memoization | Tabulation | Rolling |
|---|---|---|---|
| Direction | Top-down | Bottom-up | Bottom-up |
| Space | O(n) cache + stack | O(n) array | O(1) two variables |
| Stack risk | StackOverflow for large n | None | None |
| Subproblems | Only reachable ones | All from 0 to n | All from 0 to n |
| Best for | Sparse state spaces | Dense, sequential | When only final value needed |
What about integer overflow?
Fibonacci numbers grow exponentially. The 92nd Fibonacci number is 7,540,113,804,746,346,429, which fits in a long. The 93rd is 12,200,160,415,121,876,738, which exceeds Long.MAX_VALUE and overflows silently.
package com.bank.dsa;
import java.math.BigInteger;
public class FibBigInt {
public static BigInteger fib(int n) {
if (n == 0) return BigInteger.ZERO;
if (n == 1) return BigInteger.ONE;
BigInteger a = BigInteger.ZERO, b = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
BigInteger c = a.add(b);
a = b;
b = c;
}
return b;
}
public static void main(String[] args) {
System.out.println("fib(93) = " + fib(93));
}
}
fib(93) = 12200160415121876738
What are common mistakes?
Forgetting both base cases causes infinite recursion or wrong results.
// WRONG: only one base case
public static long fib(int n) {
if (n == 0) return 0;
return fib(n - 1) + fib(n - 2); // fib(1) calls fib(0) + fib(-1) endlessly
}
// CORRECT: both base cases
public static long fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
Using int instead of long causes overflow at fib(47). Always use long at minimum.
When should you use this in banking?
At the National Bank of India, the analytics team projects a loyalty reward balance where each month's points equal the sum of the previous two months. Customers query their projected balance at any future month.
package com.bank.service;
import java.math.BigInteger;
public class RewardProjector {
public static BigInteger project(int month) {
if (month < 0) throw new IllegalArgumentException("Month must be non-negative");
if (month == 0) return BigInteger.ZERO;
if (month == 1) return BigInteger.ONE;
BigInteger a = BigInteger.ZERO, b = BigInteger.ONE;
for (int i = 2; i <= month; i++) {
BigInteger c = a.add(b);
a = b;
b = c;
}
return b;
}
public static void main(String[] args) {
System.out.println("Month 12: " + project(12) + " points");
System.out.println("Month 100: " + project(100) + " points");
}
}
Month 12: 144 points
Month 100: 354224848179261915075 points
What should a senior engineer know?
A senior engineer should know that the naive Fibonacci is the textbook example of overlapping subproblems. The call tree has O(2^n) nodes but only O(n) distinct states, which is exactly the condition that makes DP profitable.
Matrix exponentiation can compute fib(n) in O(log n) time, and Binet's formula gives a closed-form using the golden ratio, though it suffers from floating-point precision loss for large n.
The pattern generalises to any linear recurrence with constant coefficients, and the window size determines how many rolling variables are needed.
Visual Overview
Three Approaches to Fibonacci
──────────────────────────────
1. Naive Recursion: O(2^n) time, O(n) stack
fib(5)
/ \
fib(4) fib(3) ← same subproblems!
/ \ / \
fib(3) fib(2) fib(2) fib(1)
2. Memoization: O(n) time, O(n) space
fib(5) → fib(4) → fib(3) → fib(2) → fib(1) → fib(0)
↑ cached ↑ cached ↑ cached
Each state computed once, returned from cache thereafter.
3. Rolling: O(n) time, O(1) space
[0, 1] → [1, 1] → [1, 2] → [2, 3] → [3, 5]
Two variables slide forward. No recursion, no cache.
Key Takeaway
The Fibonacci number is the classic introduction to dynamic programming. The naive recursion is correct but exponentially slow because it recomputes the same subproblems over and over. The entire point of dynamic programming is to solve each subproblem once and reuse the result.
Memoization keeps the recursion but adds a cache, collapsing the exponential call tree to O(n) time with O(n) space. The rolling bottom-up approach goes further: since each value depends only on the previous two, two variables and a loop give O(n) time with O(1) space. This is the version to ship in production.
At the National Bank of India, the analytics team used this for a loyalty reward projection where each month's points equalled the sum of the previous two months. The rolling computation returned results instantly even for distant months, and BigInteger handled the rapid growth.
The senior-level point is that Fibonacci numbers overflow a long at n = 93, so BigInteger is necessary for exact results. Matrix exponentiation computes fib(n) in O(log n) for extreme cases, but the rolling approach is the practical choice.
Remember one sentence: Fibonacci is the introduction to dynamic programming because it shows that caching overlapping subproblems converts exponential work to linear.
---