Fibonacci Series Program in Java
Fibonacci Series Program in Java using Recursion
Fibonacci series is a series whose every term is comprised of adding its previous two terms, barring the first two terms 0 and 1. Thus, we will get the series as 0, 1, 1, 2, 3, 5, 8, …...
We get the third term as 1 because its previous two terms are 0 and 1. The fourth term is 2 because its previous two terms are 1 and 1 and so on. Again, we will be discussing both the iterative as well as the recursive approach. Let us start with the iterative one.
Iterative Approach
Filename: FibonacciExample.java
public class FibonacciExample { public static void main(String[] args) { // a and b will always contain the last two terms // c will always contain the next term int a = 0, b = 1, c; int n = 6; //We are calculating the series till the 6th term. System.out.println("The first " + n + " terms of the Fibonacci series are:"); for(int j = 0; j < n; j++) { if (j == 0) System.out.print(a + " "); else if( j == 1) System.out.print(b + " "); else { //calculating next term c = a + b; System.out.print(c + " "); //Updating the last two terms a = b; b = c; } } } }
Output:
The first 6 terms of the Fibonacci series are: 0 1 1 2 3 5
Explanation: The above approach is quite easy. First, we are initializing the first two terms of the series (a = 0 and b = 1). In the first two iterations, we are printing the first two terms. From the third iteration onwards, we are calculating the next term, printing it, and then updating the last two terms to get prepared for the next iteration. Now, let us discuss the recursive approach.
Recursive Approach
Filename: FibonacciExample1.java
public class FibonacciExample1 { static int findFibonacci(int n) { if(n <= 1) return n; // recursively calling to find and add last two terms return findFibonacci(n-1) + findFibonacci(n-2); } public static void main(String[] args) { int n = 6; //We are calculating the series till the 6th term. System.out.println("The first " + n + " terms of the Fibonacci series are:"); for(int i = 0; i < 6; i++) { int no = findFibonacci(i); System.out.print(no + " "); } } }
Output:
The first 6 terms of the Fibonacci series are: 0 1 1 2 3 5
Explanation: We have seen that every term in the Fibonacci series is dependent on last two terms. Thus, if we define a function F(n) which gives the value of the nth term of the series, we get our recursion relation as:
F(n) = F(n-1) + F(n-2)
On the basis of the above relation, we have written our recursion method findFibonacci(). The if condition in the findFibonacci() method takes care of the base case: first term = 0 and second term = 1. Thus, we have:
findFibonacci(0) = 0
findFibonacci(1) = 1
findFibonacci(2) = findFibonacci(0) + findFibonacci(1) = 0 + 1 = 1
findFibonacci(3) = findFibonacci(2) + findFibonacci(1) = 1 + 1 = 2
findFibonacci(4) = findFibonacci(3) + findFibonacci(3) = 2 + 1 = 3
findFibonacci(5) = findFibonacci(4) + findFibonacci(3) = 3 + 2 = 5
Displaying Fibonacci Series Up to A Given Number
So far, we have only discussed to display the Fibonacci series up to given term (up to 6th term in our examples). However, we can also display the series up to a given number. The following example illustrates the same.
Filename: FibonacciExample2.java
public class FibonacciExample2 { public static void main(String[] args) { // a and b will always contain the last two terms // c will always contain the next term int a = 0, b = 1, c; int n = 50; //We are calculating the series up to number n. System.out.println("The Fibonacci series up to the number " + n + " are:"); while(a <= n) // Restricting the display upto n { System.out.print(a + " "); c = a + b; //finding next term //Updating last two terms a = b; b = c; } } }
Output:
The Fibonacci series up to the number 50 are: 0 1 1 2 3 5 8 13 21 34
Explanation: Here, we limited our display up to number 50 by checking the last term is less than or equal to 50 or not in the while loop.