Fibonacci Series in Java
Problem
The Fibonacci sequence is a series of numbers where each term is the sum of the two terms before it, starting from 0 and 1.
Given a count n, generate the first n numbers of the Fibonacci sequence.
Java Program
public class Fibonacci {
static int fib(int n) {
if (n <= 1) return n; // base cases: fib(0) = 0, fib(1) = 1
return fib(n - 1) + fib(n - 2); // sum of the two preceding terms
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.print(fib(i) + " ");
}
}
}Output
Core Logic
The recursive definition maps directly onto code — each term is just the sum of the two terms before it.
- 1The base cases
if (n <= 1) return n;handle the first two terms, 0 and 1, directly. - 2Every other call returns
fib(n - 1) + fib(n - 2)— the sum of the two preceding terms. - 3Each call branches into two further recursive calls, so the call tree grows wide rather than in a single line like factorial.
- 4The main loop calls
fib(i)forifrom 0 to 9 and prints each result.
0 1 1 2 3 5 8 13 21 34.Key Point: This direct recursive version recomputes the same sub-values many times — for large n, memoization or an iterative loop would be far more efficient.
Why: Each call branches into two further calls, so the total number of calls roughly doubles with every additional term, while the deepest chain of calls only ever reaches n frames.
Key Concepts
Approach 2: Iterative
public class FibonacciIterative {
public static void main(String[] args) {
int a = 0, b = 1;
for (int i = 0; i < 10; i++) {
System.out.print(a + " ");
int next = a + b; // next term is the sum of the last two
a = b;
b = next;
}
}
}
Output
Core Logic
You don't need recursion to build this — keep the last two terms in a pair of variables and slide them forward each iteration.
- 1
aandbstart at0and1— the first two Fibonacci numbers. - 2Each loop iteration prints
a, the current term. - 3
next = a + bcomputes the following term as the sum of the two most recent ones. - 4
aandbthen both shift forward —abecomes the oldb, andbbecomesnext— ready for the next iteration.
a=0, b=1, the loop prints 0, then updates to a=1, b=1, prints 1, updates to a=1, b=2, prints 1, and so on.Key Point: This runs in O(n) time with O(1) space and no repeated work — unlike the naive recursive version, each term is computed exactly once.
Why: Each term is computed once from the previous two, which are kept in just two variables that get overwritten every iteration.
Key Concepts
Approach 3: Memoized Recursion
import java.util.HashMap;
import java.util.Map;
public class FibonacciMemoized {
static Map<Integer, Integer> memo = new HashMap<>();
static int fib(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n); // cache hit — skip recomputation
int result = fib(n - 1) + fib(n - 2);
memo.put(n, result); // cache before returning
return result;
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.print(fib(i) + " ");
}
}
}
Output
Core Logic
The recursive structure can stay exactly the same — just cache each result the first time it's computed, a trick called memoization.
- 1A
HashMap<Integer, Integer>namedmemostores everyfib(n)result already computed. - 2Before computing anything,
if (memo.containsKey(n))checks whether the answer is already cached, returning it immediately if so. - 3Only on a cache miss does the function actually recurse into
fib(n - 1) + fib(n - 2). - 4The freshly computed result is stored with
memo.put(n, result)before being returned, so future calls for the samenare instant.
fib(9) only ever computes fib(0) through fib(9) once each — every repeated sub-call after the first hits the cache instead of recursing again.Key Point: The naive recursive version recomputes the same sub-values exponentially many times; memoization brings that down to O(n) time by trading a small amount of memory for avoiding repeated work.
Why: Each fib(n) is computed once and cached in the memo map, and the map plus the call stack both grow proportionally to n.
Key Concepts
Approach 4: Java 8
import java.util.stream.Stream;
public class FibonacciStream {
public static void main(String[] args) {
// Each step derives the next pair from the last, same rule as the iterative version
Stream.iterate(new int[]{0, 1}, f -> new int[]{f[1], f[0] + f[1]})
.limit(10)
.map(f -> f[0])
.forEach(term -> System.out.print(term + " "));
}
}
Output
Core Logic
Stream.iterate() can generate the whole sequence lazily — each step derives the next pair of terms from the last, with no explicit loop or recursion.
- 1
Stream.iterate(new int[]{0, 1}, f -> new int[]{f[1], f[0] + f[1]})starts from the seed pair[0, 1]and generates each next pair by sliding forward, the same rule the iterative version'sa/bswap used. - 2
.limit(10)caps the otherwise-infinite stream at the first 10 pairs. - 3
.map(f -> f[0])pulls just the first element out of each pair — the actual Fibonacci term. - 4
.forEach(...)prints each term, separated by spaces.
[0, 1] generates [1, 1], then [1, 2], then [2, 3], and so on — mapping the first element of each gives 0, 1, 1, 2, 3, ....Key Point: Stream.iterate() is lazy — it only computes as many pairs as .limit(10) asks for, so it never risks generating an infinite sequence eagerly the way a naive loop bound mistake might.
Why: Stream.iterate() only ever keeps the current pair of terms in memory, generating the next pair lazily as limit(10) pulls each one.
Key Concepts
Interview Questions
Why is plain recursion so slow for Fibonacci?
Each call branches into two more calls, and the same terms are recomputed again and again, so the work grows roughly as O(1.6ⁿ). Computing the 40th term this way already takes hundreds of millions of calls.
How does memoization fix it?
It stores each term the first time it's computed, in an array or map, and returns the stored value on later calls. Every term is then calculated only once, bringing the cost down to O(n).
What is the most memory-efficient approach?
The iterative version with two variables. It keeps only the previous two terms, so it runs in O(n) time with O(1) extra space.