Fibonacci series in Java

You shall find a lot of articles on the Fibonacci series in Java out there on the internet. Then why read this one? In this article, we are going to learn how to print the Fibonacci series and improve the algorithm step by step.

We shall start with recursion improve with memoization and finally implement a top-down dynamic approach. Lastly, we shall see how mathematics makes our lives easy!

What is the Fibonacci series?

In this series, every term is the sum of the previous 2 terms. So, the nth term is equal to (n-1)th term plus (n-2)th term.

The first 2 terms are defined as 0 and 1. From this, we can keep building the Fibonacci series to any number of terms using this simple formula.

For instance, the series 1 1 2 3 5 8 13 21 is a Fibonacci series with 8 elements.

Fibonacci Series in Java using Recursion

In a recursive program, we repetitively solve sub-problems which leads to the final solution. Let’s write a Java program to calculate the nth Fibonacci term using recursion.

Code

public class FibRec {
	static int fibonacci(int n) {
		if(n <= 1)
			return n;
		return fibonacci(n-1)+fibonacci(n-2);
	}
	public static void main(String[] args) {
		System.out.println(fibonacci(8));
	}
}

Output

21

The above code returns the 8th Fibonacci term.

For every value of n, the above formula is used to calculate results.

For example, when n was 4, fibonacci(3) and fibonacci(2) are calculated and added.

The minimum value of n for which the formula is used is 2. Below that we return n itself.

This is our base case. For n=1 we return 1. For n=0 we return 0. Therefore, if n is less or equal to 1 we return n itself.

Fibonacci using Memoization

In the above solution, we can notice that fib(2) has been calculated multiple times.

Well, the Fibonacci series is an ideal example of overlapping sub-problems.

So, we can improve the above algorithm using memoization. In this technique, we create a lookup table where we store the calculated result for every value from 0 to n. In this way, we don’t have to solve the same problems repeatedly.

Code

public class FibMem {
	static int lookup[];
	static int fibonacci(int n) {
		if(lookup[n] != -1)
			return lookup[n];
		if(n <= 1) {
			lookup[n] = n;
			return n;
		}
		lookup[n] = fibonacci(n-1)+fibonacci(n-2);
		return lookup[n];
	}
	public static void main(String[] args) {
		int n = 6;
		lookup = new int[n+1];
		for(int i=0; i<n+1; i++) {
			lookup[i] = -1; //set default to -1
		}
		System.out.println(fibonacci(n));
	}
}

Output

8

The above recursion tree clearly shows how many repeating sub-problems were optimized using our lookup table.

In conclusion, before returning the value of fib(n) store in lookup[n]. Before computing check, if lookup[n] is already processed. If so, return lookup[n].

Fibonacci using Dynamic Approach

Here, we shall remove recursion completely and use the lookup table only.

Normally a dynamic programming table contains rows as well as columns. However, in this case, we can see that the function takes only one input parameter fibonacci(int n).

In conclusion, we can say that the number of parameters of the method determines the dimension of the lookup table. In this case, it is 1.

So, we use a one-dimensional lookup array.

Code

public class fibDp {
	static int dp[];
	static int fibonacci(int n) {
		for(int i = 0; i<n+1; i++) {
			if(i<=1)// base case
				dp[i] = i;
			else {
				dp[i] = dp[i-1] + dp[i-2];
			}
		}
		return dp[n];
	}
	public static void main(String[] args) {
		int n = 6;
		dp = new int[n+1];
		System.out.println(fibonacci(n));
	}
}

Output

8

Compare the dynamic solution with the recursive one for better understanding. To get the result of fib(6), we have computed fib(0), fib(1), fib(2) … fib(6).

Just like memoization, we have calculated every value of n only once. So both the algorithms have a time complexity of O(n).

Now the question is which one is better?

Well, the Dynamic approach is better because it does not involve recursion at all. So, in the case of large inputs, there are no risks of StackOverflow error.

As you can imagine that even for n=100 the recursion tree will be huge and cause problems to compute. But dynamic programming needs only an array of size n.

Print Fibonacci Series in java

Now we already know that the dynamic approach is the best to calculate Fibonacci numbers. Let’s modify it to print the series. All we have to do is print the DP table that already contains all the values of fib(0) to fib(n).

Code

public class fibDp {
	static int dp[];
	static int fibonacci(int n) {
		for(int i = 0; i<n+1; i++) {
			if(i<=1)// base case
				dp[i] = i;
			else {
				dp[i] = dp[i-1] + dp[i-2];
			}
		}
		return dp[n];
	}
	static void printTable(int table[]) {
		for(int i=0; i<table.length; i++) {
			System.out.print(table[i]+" ");
		}
		System.out.println();
	}
	public static void main(String[] args) {
		int n = 20;
		dp = new int[n+1];
		
		System.out.println(n+"th term: "+fibonacci(n));
		System.out.println("series:");
		printTable(dp);
	}
}

Output

20th term: 6765
series:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 

Only the printTable(int table[]) method has been added. It simply prints an array.

Is there an even better way?

In the beginning when I said, “We shall see how mathematics makes our lives easy!”, I meant it. By now we have understood that calculating Fibonacci numbers can be tedious.

Lucky for us, the French mathematician Jacques Binet discovered a mathematical equation to directly calculate the value of fib(n). Binet’s Formula: the nth Fibonacci number is given by:

The simplified Binet’s formula is given by:

Code

public class FibBinet {
	static double fibonacci(int n) {
		return Math.pow(((1+Math.sqrt(5))/2), n)/Math.sqrt(5);//simplified formulae
	}
	public static void main(String[] args) {
		int n = 20;
		System.out.println(n+"th fibonacci term: "+Math.round(fibonacci(n)));
	}
}

Output

20th fibonacci term: 6765

Boom! Time Complexity O(1). We used Math.sqrt() to compute the square root of 5.

Directly the simplified Binet’s equation has been used here.

This formula can also be used to calculate Fibonacci for large values of n.

However, the formulae return a decimal answer close to the actual answer. Therefore, we rounded it up using Java Math.round().

See our article on Java recursion.

Like this article? Follow us on Facebook and LinkedIn. You can also subscribe to our weekly Feed.