Fibonacci Series Program in Java

Last Updated on September 22, 2023 by Mayank Dham

Within this article, we will delve into the intricacies of the Fibonacci series Program in Java. Furthermore, we shall acquire the knowledge to construct a Java program for generating the Fibonacci series, employing diverse techniques including iterative, recursive, and recursive with memoization. Additionally, we will analyze the time and space complexities associated with each of these 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 34

Conclusion
In 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.

In conclusion, the Fibonacci series is a fundamental mathematical sequence that holds significant relevance in various fields, including computer science and mathematics. Implementing the Fibonacci series program in Java offers insights into different programming techniques, such as iterative, recursive, and recursive with memoization. Understanding the trade-offs between these methods in terms of time and space complexity can aid in choosing the most suitable approach for specific use cases. Mastering the Fibonacci series program not only showcases programming skills but also provides a deeper understanding of algorithmic thinking and problem-solving.

Frequently Asked Questions (FAQs) about Fibonacci Series Program in Java:

Some of the FAQs related to Fibonacci Series Program in Java are discussed below:

1. What are the different methods to generate the Fibonacci series in Java?
There are several methods to generate the Fibonacci series in Java, including iterative, recursive, and recursive with memoization approaches.

2. What is an iterative approach to generating the Fibonacci series?
In the iterative approach, each term is calculated based on the two previous terms using a loop.

3. What is a recursive approach to generating the Fibonacci series?
In the recursive approach, a function calls itself to calculate the Fibonacci terms. However, this method can lead to exponential time complexity.

4. What is the recursive approach with memoization?
The recursive approach with memoization involves storing the results of expensive function calls and reusing them to avoid redundant calculations. This significantly improves the time complexity of the algorithm.

5. What is the time complexity of the iterative Fibonacci program?
The time complexity of the iterative Fibonacci program is O(n), where n is the term number in the series.

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