The Fibonacci sequence is a series of numbers where each number is found by adding up the two numbers before it.
0, 1, 1, 2, 3, 5, 8, 13, 21, …
It’s a commonly asked interview question for entry level positions. In this post, I’ll show you how to generate Fibonacci series in Java using three different approaches from simple recursion to memoization to using Java 8 streaming API.
Let’s start.
1. Fibonacci Using Recursion
The following algorithm illustrates how to generate Fibonacci sequence in Java using recursion. It will generate first 10 numbers in the sequence.
package com.codeahoy.ex;
public class Main {
public static void main(String[] args) {
// first 10 Fibonanni numbers
final int MAX_NUMS = 10;
for (int i = 1; i <= MAX_NUMS; i++) {
System.out.print(fib(i) + ", ");
}
System.out.println("..."); // Print nice
}
public static long fib(int n) {
if (n <= 1) {
return n;
} else {
return fib(n - 1) + fib(n - 2);
}
}
}
Output*
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
This recursive algorithm is very inefficient because it will take a very long to compute larger digits in the series. Try setting n=48 and run this algorithm to see for yourself. It will take a few seconds to complete. This is because each step of the algorithm computes the sum of previous two numbers over and over again. For fib(5), fib(3) is computed twice.
fib(5) = fib(4) + fib(3)
fib(3) = fib(2) + fib(1)
fib(4) = fib(3) + fib(2)
fib(2) = fib(1) + fib(0)
This algorithm is also buggy. For large values of Fibonacci series, it will result in overflow (which we aren’t checking for to keep it simple.)
2. Fibonacci Using Recursion with Memoization
Let’s improve the algorithm above to add memoization to improve its performance. According to wikipedia:
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
In the following algorithm, we introduce a cache (an array) to store results after we compute them the first time. Next time when we need Fibonacci number for a given index, we first check to see if we have it in the cache. If we do, we just return it. If we don’t have it, we compute it and store it in the cache, before returning it. This algorithm is much more performant compared to the last algorithm because it avoids doing the same computations over and over again.
package com.codeahoy.ex;
public class Main {
private static final int MAX_NUMS = 45;
// A cache to hold results
private final static long[] fibCache =
new long[MAX_NUMS];
public static long fib(int n) {
if (n <= 1) {
return n;
} else if (fibCache[n] != 0) {
// we found previous computed result
// just return it.
return fibCache[n];
} else {
long l = fib(n - 1) + fib(n - 2);
fibCache[n] = l;
return fibCache[n];
}
}
public static void main(String[] args) {
for (int i = 1; i < MAX_NUMS; i++) {
System.out.print(fib(i) + ", ");
}
System.out.println("..."); // Print nice
}
}
3. Fibonacci Using Java 8 Streams
You can also generate Fibonacci series using Java 8 streams. The following code shows how this is done.
package com.codeahoy.ex;
import java.util.stream.Stream;
public class Fibonacci {
public final int previous;
public final int value;
private static final int MAX_NUMS = 10;
// Seed for stream.iterate()
public static final Fibonacci SEED =
new Fibonacci(1, 1);
public Fibonacci(int previous, int value) {
this.previous = previous;
this.value = value;
}
public Fibonacci next() {
return new Fibonacci(value, value + previous);
}
@Override
public String toString() {
return String.valueOf(value);
}
public static void main(String[] args) {
System.out.print(Fibonacci.SEED + ", "); // Print 1st
Stream.iterate(Fibonacci.SEED, Fibonacci::next)
.limit(MAX_NUMS)
.forEach(x -> System.out.print(x + ", "));
System.out.println("..."); // Print nice
}
}
That’s all.
Fun Fact: November 23rd or 11/23 is celebrated as Fibonacci Day because it has the digits “1, 1, 2, 3” which form the sequence. Fibonacci series is one of the most famous mathematical formulas and commonly occurs in nature. Watch this excellent Ted Talk on the magic of Fibonacci numbers.