How to Generate Fibonacci Sequence in Java

What is Fibonacci?

A sequence where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

Solutions

Method 1: Using Loop

java

public class Main {
    public static void main(String[] args) {
        int n = 10;
        int first = 0, second = 1;
        
        System.out.print("Fibonacci Series: " + first + " " + second);
        
        for (int i = 2; i < n; i++) {
            int next = first + second;
            System.out.print(" " + next);
            first = second;
            second = next;
        }
    }
}
// Output: Fibonacci Series: 0 1 1 2 3 5 8 13 21 34

Method 2: Using Recursion

java

public static int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// Usage - Print first 10 numbers
for (int i = 0; i < 10; i++) {
    System.out.print(fibonacci(i) + " ");
}
// Output: 0 1 1 2 3 5 8 13 21 34

Method 3: Using Memoization (Optimized)

java

import java.util.HashMap;

static HashMap<Integer, Long> memo = new HashMap<>();

public static long fibonacci(int n) {
    if (n <= 1) return n;
    
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    
    long result = fibonacci(n - 1) + fibonacci(n - 2);
    memo.put(n, result);
    return result;
}

// Much faster for large n!
System.out.println(fibonacci(50)); // 12586269025

Did You Know?

The Fibonacci sequence appears in nature! Flower petals, pine cones, and spiral galaxies often follow this pattern. It's also related to the Golden Ratio (φ ≈ 1.618)!

Watch Out!

Simple recursion is very slow for large n! fibonacci(40) takes seconds, but memoization makes it instant. Always use memoization or iteration for better performance.

Real-World Use Cases

Nature: Modeling population growth
Art: Creating aesthetically pleasing compositions
Algorithms: Dynamic programming examples
Finance: Fibonacci retracement in trading

›Short versionOpen if you only have a minute.

Each term is the sum of the previous two. The usual start is 0, 1.
Keep two variables. A recursive method that calls itself twice repeats the same work.
Update a temporary next before overwriting either previous term.
F(47) does not fit in an int. The loop is fast; the type is the limit.

Fibonacci

Generate numbers where each term is the sum of the previous two terms.

Working approach

Agree whether n is a count of terms or an index before writing the loop.
Hold the previous two values and append their sum.
Use the recursive form only to see the repeated calls. Do not use it for a large n.

Walk the sample

Start 0, 1
Next is 0 + 1 = 1
Next is 1 + 1 = 2
Next is 1 + 2 = 3

The trap

Writing a = b; b = a + b drops the old a, because a was already overwritten. The next pair is wrong from that step on.

java

static int nth(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("negative index");
    }
    int previous = 0;
    int current = 1;
    for (int i = 0; i < n; i++) {
        int next = Math.addExact(previous, current);
        previous = current;
        current = next;
    }
    return previous;
}

Why does the two-call recursive fib(n) become unusable long before the int overflows?

fib(n) calls fib(n - 1) and fib(n - 2), and those calls do not share results. The number of calls grows like phi^n.

The iterative pair of variables is O(n) additions and O(1) extra space. Separately, F(47) is 2971215073 and does not fit in an int, so addExact is the overflow guard.

The loop is O(n) time and O(1) extra space. The naive recursion is exponential.

Easy to get wrong

Overwriting one variable before saving the other.
Using the two-recursive-call version for a large n.