Java Fibonacci Series Program: Loop, Recursion and Memoization

The Fibonacci series starts with 0, 1 and every next number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13... Here are three ways to write it in Java.

1. Using a loop (the best way)

public class Main {
    public static void main(String[] args) {
        int count = 12;
        long a = 0, b = 1;
        for (int i = 0; i < count; i++) {
            System.out.print(a + " ");
            long next = a + b;
            a = b;
            b = next;
        }
        System.out.println();
    }
}

2. Using recursion

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

    public static void main(String[] args) {
        for (int i = 0; i < 12; i++) {
            System.out.print(fib(i) + " ");
        }
        System.out.println();
    }
}

This is simple, but it calculates the same values again and again. It becomes very slow for numbers like fib(45).

3. Recursion with memoization

We save each answer in a map, so it is calculated only once.

import java.util.HashMap;
import java.util.Map;

public class Memo {
    static Map<Integer, Long> cache = new HashMap<>();

    static long fib(int n) {
        if (n <= 1) return n;
        if (cache.containsKey(n)) return cache.get(n);
        long value = fib(n - 1) + fib(n - 2);
        cache.put(n, value);
        return value;
    }

    public static void main(String[] args) {
        System.out.println(fib(10));
        System.out.println(fib(50));
        System.out.println(fib(90));        // the biggest one which fits in a long is fib(92)
    }
}

Which one to use?

Way	Speed	Note
Loop	Very fast	Simple and uses no extra memory
Plain recursion	Very slow for big n	Good only to learn recursion
Memoization	Fast	Uses memory for the cache, and deep recursion for a big n

Related: Java Recursion and Java HashMap.

• Next Code

---

Tutorials
No Content Found.

Exercises & Assignments
No Content Found.

Interview Questions & Answers
No Content Found.