Fibonacci Numbers in Java

Fibonacci numbers are elements of the numerical sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …, in which the first two numbers are 0 and 1, and each subsequent number equals the sum of the two preceding ones. In this lesson we compute the n-th Fibonacci number in Java two ways — iteratively with a for loop and recursively — and compare their speed.

Fibonacci formula

Mathematically the sequence is defined by a recurrence relation: the first two terms are fixed, and each following term is the sum of the two on its left:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2), for n > 1

Two implementation approaches follow directly from this formula: the iterative one (go bottom-up in a loop, keeping the two most recent values) and the recursive one (literally repeat the formula by calling the function for n-1 and n-2).

Fibonacci with a for loop

The iterative approach is the fastest and most practical. We keep only the two previous numbers and slide the «window» forward on each step. The time complexity is linear — O(n).

private static long calculateWithFor(int n) {
    if (n <= 1) {
        return n;
    }
    long first = 0;   // F(0)
    long second = 1;  // F(1)
    long result = 0;
    for (int i = 2; i <= n; i++) {
        result = first + second;
        first = second;
        second = result;
    }
    return result;
}

The loop runs exactly n-1 times and needs no array — three variables are enough. This is how you should compute Fibonacci numbers in real code.

Fibonacci with recursion

The recursive version repeats the mathematical formula verbatim: the method calls itself for n-1 and n-2 until it reaches the base cases F(0) = 0 and F(1) = 1. It looks elegant, but that elegance is expensive — the complexity is exponential, O(2^n).

private static long recursive(int n) {
    if (n <= 1) {
        return n;
    }
    return recursive(n - 1) + recursive(n - 2);
}

Why so slow? Because the same values are recomputed again and again. When you call recursive(5), for example, F(2) is calculated three times and F(1) five times. The call tree grows exponentially, so around n = 45–50 the program starts to lag noticeably, and at n = 250 it effectively freezes.

Speed and complexity comparison

To see the difference for real, let's time both algorithms. For measurement we use System.nanoTime() — the right tool for micro-benchmarks (unlike LocalTime, which has low resolution):

public class FibonacciExample {
    public static void main(String[] args) {
        int n = 45;

        long start1 = System.nanoTime();
        long r1 = recursive(n);
        long time1 = System.nanoTime() - start1;
        System.out.println("Recursion: " + r1 + ", time: " + time1 / 1_000_000 + " ms");

        long start2 = System.nanoTime();
        long r2 = calculateWithFor(n);
        long time2 = System.nanoTime() - start2;
        System.out.println("For loop: " + r2 + ", time: " + time2 / 1_000_000 + " ms");
    }

    private static long calculateWithFor(int n) {
        if (n <= 1) {
            return n;
        }
        long first = 0;
        long second = 1;
        long result = 0;
        for (int i = 2; i <= n; i++) {
            result = first + second;
            first = second;
            second = result;
        }
        return result;
    }

    private static long recursive(int n) {
        if (n <= 1) {
            return n;
        }
        return recursive(n - 1) + recursive(n - 2);
    }
}

Both approaches return the same value, but the time differs by orders of magnitude:

Recursion: 1134903170, time: 4300 ms
For loop: 1134903170, time: 0 ms

The iterative version answers instantly, while the recursive one already thinks for several seconds at n = 45. Here is how the approaches compare:

Large numbers and long overflow

Fibonacci numbers grow very fast, so a fixed-size type quickly becomes too small. F(92) = 7540113804746346429 is the last term of the sequence that still fits in a long. From F(93) onward the value overflows, and the method silently returns an incorrect (often negative) result — no exception is thrown.

If you need Fibonacci numbers for large n, use BigInteger — it supports integers of arbitrary length:

import java.math.BigInteger;

private static BigInteger fibonacci(int n) {
    BigInteger first = BigInteger.ZERO;
    BigInteger second = BigInteger.ONE;
    for (int i = 2; i <= n; i++) {
        BigInteger next = first.add(second);
        first = second;
        second = next;
    }
    return n == 0 ? BigInteger.ZERO : second;
}

Common mistakes

• Using plain recursion for large n. Around n = 45–50 the program lags noticeably, and at 250 it effectively freezes because of the exponential complexity. Use a loop or memoization.
• long overflow. After F(92) the result in a long becomes incorrect. For larger values you need BigInteger.
• Timing with LocalTime. For benchmarks use System.nanoTime(): it has high resolution and does not depend on the system clock or the midnight rollover.
• Confusing the indexing. Agree upfront where the sequence starts — at F(0) = 0 or F(1) = 1. That determines which number counts as the "first".