Fibonacci Sequence 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.
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.
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.