The Fibonacci series starts 0, 1 and every next term is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, 13, 21, …. In Java there are five sensible ways to write it, and they differ wildly: one takes about 331 million calls to find the 40th term and another needs one loop.
| Method | Time | Extra space | Use it when |
|---|---|---|---|
| Loop | O(n) | O(1) | Almost always |
| Plain recursion | O(2n) upper bound (about 1.618n in practice) | O(n) stack | Teaching recursion, never production |
| Memoized recursion | O(n) | O(n) cache and stack | When the recursive form is clearer |
| Stream.iterate | O(n) | O(1) | You want a lazy infinite sequence |
| BigInteger loop | O(n) additions on growing numbers | O(n) digits | Terms beyond fib(92) |
Tested on OpenJDK 21.0.12. All output below comes from one run of FibonacciSeries.java. The largest Fibonacci number that fits in alongis fib(92); fib(93) silently wraps to a negative number unless you useMath.addExactorBigInteger.
1. Loop: the one to use
Keep the last two terms in a and b. Each step replaces them with b and a + b.
static long fibLoop(int n) {
long a = 0, b = 1; // fib(0), fib(1)
for (int i = 0; i < n; i++) {
long next = a + b;
a = b;
b = next;
}
return a;
}First 15 terms: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377Source: FibonacciSeries.java, method fibLoop.
2. Plain recursion, and why it is so slow
The definition translates directly: fib(n) = fib(n−1) + fib(n−2). But each call starts two more, and the two branches recompute the same values again and again.
The tree for fib(5) has 15 calls. fib(3) is computed twice, fib(2) three times and fib(1) five times, and that waste doubles as n grows. The number of calls for fib(n) is exactly 2 × fib(n+1) − 1, which the program confirms by counting actual calls:
static long calls; // counts invocations, for the demo only
static long fibRecursive(int n) {
calls++;
if (n < 2) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}n fib(n) calls (naive) 2*fib(n+1)-1
1 1 1 1
2 1 3 3
3 2 5 5
5 5 15 15
10 55 177 177
20 6765 21891 21891
30 832040 2692537 2692537Source: FibonacciSeries.java.
The call count grows by a factor of about 1.618 per step, so the true bound is O(1.618n), which is inside the usual “O(2n)”. In practice, fib(40) took 594 ms and made 331,160,281 calls:
naive fib(40) = 102334155 calls=331160281 594 ms
memo fib(40) = 102334155 5 usSource: FibonacciSeries.java.
3. Memoization: remember what you computed
Cache each result the first time and the tree collapses to a single chain of n calls. The cache is the only change, and it turns O(2n) into O(n).
static final Map<Integer, Long> cache = new HashMap<>();
static long fibMemo(int n) {
if (n < 2) return n;
Long hit = cache.get(n);
if (hit != null) return hit;
long value = fibMemo(n - 1) + fibMemo(n - 2);
cache.put(n, value);
return value;
}The memoized fib(40) from the output above finished in microseconds, against hundreds of milliseconds for the plain version. Source: FibonacciSeries.java, method fibMemo.
4. Streams: a lazy sequence of pairs
Carry the pair (a, b) as the stream element. Stream.iterate produces (0,1), (1,1), (1,2), (2,3), …; take the first element of the pair at position n.
static long fibStream(int n) {
return Stream.iterate(new long[]{0, 1}, p -> new long[]{p[1], p[0] + p[1]})
.skip(n)
.findFirst()
.get()[0];
}Source: FibonacciSeries.java.
The program checks that loop, memo, stream and BigInteger agree for every n from 0 to 40 (and recursion up to 25): All five agree for n = 0..40: true. See Top 50 Java Stream API coding interview questions for more stream patterns.
5. BigInteger and the overflow at n = 93
A long holds up to 9,223,372,036,854,775,807. fib(92) is 7,540,113,804,746,346,429, which fits. fib(93) is 12,200,160,415,121,876,738, which does not. Java does not throw: it wraps around to a negative number.
fib(92) = 7540113804746346429 (largest that fits in long)
fib(93) with plain long = -6246583658587674878 <- wrapped around
fib(93) with addExact -> java.lang.ArithmeticException: long overflow
fib(93) as BigInteger = 12200160415121876738
fib(100) as BigInteger = 354224848179261915075
fib(1000) has 209 digitsstatic long fibExact(int n) {
long a = 0, b = 1;
for (int i = 0; i < n; i++) {
long next = Math.addExact(a, b); // throws ArithmeticException instead of wrapping
a = b;
b = next;
}
return a;
}static BigInteger fibBig(int n) {
BigInteger a = BigInteger.ZERO, b = BigInteger.ONE;
for (int i = 0; i < n; i++) {
BigInteger next = a.add(b);
a = b;
b = next;
}
return a;
}Source: FibonacciSeries.java.
Math.addExact turns silent wrap-around into an ArithmeticException. BigInteger has no limit: fib(1000) has 209 digits. For overflow in other arithmetic, see adding two integers without overflow and the factorial program, which overflows even sooner.
Print the first n terms
Call the loop version for each index, or keep a rolling pair and print as you go. The first line of the output shows the first 15 terms:
First 15 terms: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377Source: FibonacciSeries.java.
Common interview questions
What is the time complexity of recursive Fibonacci?
Exponential: about 1.618n calls, usually quoted as O(2n). The call count is exactly 2×fib(n+1)−1.
How does memoization fix it?
Each fib(k) is computed once and cached, so there are only n distinct calls: O(n) time and O(n) space.
What is the largest Fibonacci number that fits in a long?
fib(92) = 7,540,113,804,746,346,429. fib(93) overflows.
Can you compute Fibonacci in O(1) space?
Yes, the loop version keeps only the last two terms.
Is there a faster way than O(n)?
Yes: matrix exponentiation or the fast-doubling identities compute fib(n) in O(log n) multiplications. This page does not implement them.
Common mistakes
- Using recursion for n above about 40. The call count passes 300 million.
- Using
int. It overflows at fib(47); uselongup to 92 andBigIntegerbeyond. - Starting from 1, 1 and then printing wrong indexes. Decide whether fib(0) is 0 and keep it consistent.
- Memoizing with a
HashMapandcomputeIfAbsentrecursively. It can throwConcurrentModificationExceptionbecause the recursive call modifies the map inside the lambda. The explicitgetandputabove avoids that. - Trusting a negative result. A negative Fibonacci number means overflow, not a bug in the recurrence.
FAQ
How do I write the Fibonacci series in Java?
Keep two variables for the last two terms and add them in a loop. The loop version is the standard answer.
Why is recursive Fibonacci slow?
It recomputes the same values exponentially many times, as the recursion tree shows.
How do I print Fibonacci numbers up to 100 digits?
Use BigInteger, because long stops at fib(92).
Can I generate Fibonacci with streams?
Yes, with Stream.iterate(new long[]{0, 1}, p -> new long[]{p[1], p[0] + p[1]}).
No Comments yet!