In this article, we will learn what is the Fibonacci series. We will also learn how to write the Fibonacci series program in java using various methods like iterative, recursive, and recursive with memoization. We will also discuss the time and space complexity of all the methods.
What is the Fibonacci series?
In the Fibonacci series, the next term is an addition of the previous two terms. For example, if the previous two terms are 3 and 5 then the next term will be 8 (3+5). The first two terms of the Fibonacci series are 0 and 1 respectively. Now, if we look at the third term it will be the summation of the first term(0) and the second term(1) is 1 (0+1). If we look for the fourth term it will be the addition of the second term(1) and the third term (1) is 2(1+1). Using the same approach we can find the remaining terms easily.
In the above image, we can see the first ten terms of the Fibonacci series. We can clearly observe that apart from the first two terms every term is the sum of its previous two terms. Now, we have an idea about how the Fibonacci series is constructed. So let’s see various approaches to writing the Fibonacci series program in java.
Approach 1: Iterative method for the Fibonacci series program in java
In this iterative method, we will use the first two terms of the Fibonacci series 0 and 1, and then we will find further terms using these two terms. Let’s see how to write the Fibonacci series program in java using this method.
// iterative fibonacci program in java
class PrepBytes {
public static void main(String[] args) {
int first_term=0;
int second_term=1;
int second_last_term=0;
int last_term=1;
System.out.println("The first 10 terms of the Fibonacci series are:");
for(int i=0;i<10;i++){
if(i==0){
System.out.print(first_term+" ");
}
else if(i==1){
System.out.print(second_term+" ");
}
else{
int current_term=second_last_term+last_term;
System.out.print(current_term+" ");
second_last_term=last_term;
last_term=current_term;
}
}
}
} Output:
The first 10 terms of the Fibonacci series are:
0 1 1 2 3 5 8 13 21 34 In the above Fibonacci program in java, first, we have defined the initial two terms 0 and 1. After that, we have also created two more variables last_term and second_last_term to keep track of the last and second last term so far. Now, we will run a for loop 10 times to print the first 10 terms of the Fibonacci series. In the loop, if i is less than 2 then we will directly print the first two terms, and if i is greater than or equal to 2 then first we will compute the current term which equals the sum of the last and second last term. Now, we will change the second last term as the last term and the last term as the current term to calculate further terms. In the output, we can see that the first ten terms of the Fibonacci series are printed.
Time Complexity: O(n)
Auxiliary Space Complexity: O(1)
Approach 2: Recursive method for the Fibonacci series program in java
In this approach, we will use base case as the first two terms and our recursive formula for the nth term will be (n-1)th term +(n-2)th term. Let’s see how to write the Fibonacci series program in java using the recursive method.
// recursive fibonacci program in java
class PrepBytes {
static int fibonacci(int n)
{
if (n < 2)
return n;
return fibonacci(n - 1)
+ fibonacci(n - 2);
}
public static void main(String args[])
{
System.out.println("The first 10 terms of the Fibbonaci series are:");
for (int i = 0; i < 10; i++) {
System.out.print(fibonacci(i) + " ");
}
}
}
Output:
The first 10 terms of the Fibonacci series are:
0 1 1 2 3 5 8 13 21 34 In the above Fibonacci program in java, we have written a recursive method Fibonacci. In that method, we have given base case (recursion termination condition) if the given number is less than 2 then we will return that number. Otherwise, we will find the n-1 term [fibonacci(n-1)] and the n-2 term [fibonacci(n-2)] and we will return the sum of both terms. In the output, we can see that the first ten terms of the Fibonacci series are printed.
Time Complexity: O(2^n)
Auxiliary Space Complexity: O(1)
Approach 3: Recursion + Memoization method for the Fibonacci series program in java
In this method, we will use the above recursion method the only difference is that we will use the memoization method with this approach. Memoization means we will store the answer to all the calculated terms so that we can use them again and we do not need to find that term again and again.
// recursive + memoization fibonacci program in java
class PrepBytes {
static int fibonacci(int n,int[] memo)
{
if (memo[n]!=-1){
return memo[n];
}
if (n < 2)
return n;
int current_term= fibonacci(n - 1,memo) + fibonacci(n - 2,memo);
memo[n]=current_term;
return current_term;
}
public static void main(String args[])
{
int[] memo= new int[10];
for(int i=0;i<10;i++){
if(i<2){
memo[i]=i;
}
else{
memo[i]=-1;
}
}
System.out.println("The first 10 terms of the Fibbonaci series are:");
for (int i = 0; i < 10; i++) {
System.out.print(fibonacci(i,memo) + " ");
}
}
}
Output:
The first 10 terms of the Fibonacci series are:
0 1 1 2 3 5 8 13 21 34In the above Fibonacci program in java, we have created an array of size 10 to store calculated terms and we will initialize the first two terms as 0 and 1 in that array. After that, we will use the same recursive method as above to find the nth term of the Fibonacci series. Now, when we call a method Fibonacci to find the nth term we have two options. One is, if the nth term is already calculated then we will directly return the answer. Otherwise, we will calculate the answer and store the answer in an array while returning from the recursive call. In the output, we can see that the first ten terms of the Fibonacci series are printed.
Other Java Programs
Java Program to Add Two Numbers
Java Program to Check Prime Number
Java Program to Check Whether a Number is a Palindrome or Not
Java Program to Find the Factorial of a Number
Java Program to Reverse a Number
Java Program to search an element in a Linked List
Program to convert ArrayList to LinkedList in Java
Java Program to Reverse a linked list
Java Program to search an element in a Linked List
Anagram Program in Java
Inheritance Program in Java
Even Odd Program in Java
Hello World Program in Java
If else Program in Java
Binary Search Program in Java
Linear Search Program in Java
Menu Driven Program in Java
Package Program in Java
Leap Year Program in Java
Array Programs in Java
Linked List Program in Java
String Programs in Java
Star Program in Java
Number Pattern Program in Java
For Loop Program In Java
Pattern Program in Java
String Palindrome Program in Java
Thread Program in JAVA
Java Scanner Program
While Loop Program in Java
Bubble Sort Program in Java