Home » Core Java » Fibonacci Java Example

About Santosh Balgar

Santosh Balgar
He is a Software Engineer working in an industry-leading organization. He has completed his bachelors from Visweswaraya Technological University. In his career, he has worked in designing and implementing various software systems involving Java/J2EE, Spring/ Spring Boot, React JS, JQuery, Hibernate and related database technologies. He loves to share his knowledge and always look forward to learning and explore new technologies. He loves to spend his free time with his family. He enjoys traveling and loves to play cricket.

Fibonacci Java Example

In this article, we are going to look at the Fibonacci series of numbers and how they can be generated in Java in various ways like recursion and using the classical loop. Fibonacci series generation is a classic interview question for entry-level programmers.

1. What is the Fibonacci series?

The Fibonacci series is a series of numbers in which the next number is found by adding two previous numbers. For example, Fibonacci series looks as below,

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 and so on

  • The first number is 0 and the second number is 1
  • The third number 1 is found by adding previous 2 numbers 0 and 1
  • The fourth number 2 is found by adding previous 2 numbers 1 and 1
  • The fifth number 3 is found by adding previous 2 numbers 1 and 2
  • The sixth number 5 is found by adding previous 2 numbers 2 and 3
  • And the list continues with the same pattern

This pattern can be broken down to a formula,

n0123456789
x(n)0112358132134

Let us assume 4th term can be represented as x(4) and the fifth term can be represented as x(5). In general, each term can be represented as x(n).

As per the pattern 6th term can be written as x(6) = x(4) + x(5). So formula can be written as,

x(n) = x(n-2) + x(n-1)

Here x(n) is the nth term, x(n-1) is teh previous term and x(n-2) is the term previous to that.

2. Fibonacci in Java with recursion

In this section, we are going to see how can we generate the Fibonacci series using recursion. Here we use the divide and conquer approach. In the divide and conquer technique the problem is broken down to two or more problems of the same or related type until it becomes simple enough to solve.

FibonacciGeneratorWithRecusion
import java.util.Scanner;

/**
 * @author Santosh Balgar Sachchidananda
 * FibonacciGeneratorWithRecusion generats Fibonacci series using recursion
 */
public class FibonacciGeneratorWithRecusion {

    private int generateFibonacciNumber(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        return generateFibonacciNumber(n - 1) + generateFibonacciNumber(n - 2);
    }

    public static void main(String[] args) {
        FibonacciGeneratorWithRecusion fg = new FibonacciGeneratorWithRecusion();
        System.out.println("************** Generating Fibonacci Series using recursion *****************");
        System.out.println("Enter number upto which Fibonacci series to print: ");
        int number = new Scanner(System.in).nextInt();
        for (int i = 0; i <= number; i++) {
            System.out.print(fg.generateFibonacciNumber(i) + " ");
        }
    }
}

Let us analyze the time complexity of this algorithm. To calculate nth term we need to calculate (n-1)th and (n-2)th term plus adding them together to generate the final answer.

O(n) = O(n-1) + O(n-2) + O(1)

Recursive way to generate the Fibonacci number is costly.

3. Fibonacci in Java with for loop

In this section, we will see how can we generate the Fibonacci series using a simple for loop approach.

FibonacciGeneratorWithLoop
import java.util.Scanner;

public class FibonacciGeneratorWithLoop {

    public static void main(String[] args) {
        int previousNum = 1;
        int secondPreviousNum = 0;

        System.out.println("************** Generating Fibonacci Series with loop *****************");
        System.out.println("Enter number upto which Fibonacci series to print: ");

        int number = new Scanner(System.in).nextInt();

        for (int i = 1; i <= number; i++) {
            if (i == 1) {
                System.out.print("0 ");
            } else if (i == 2 || i == 3) {
                secondPreviousNum = 1;
                previousNum = 1;
                System.out.print(" 1");
            } else {
                int fibonacciNum = previousNum + secondPreviousNum;
                System.out.print(fibonacciNum + " ");
                secondPreviousNum = previousNum;
                previousNum = fibonacciNum;
            }
        }
    }
}

Let us analyze the time complexity of this approach.

This approach is linear and we have to iterate through n time. Hence, the time complexity of the loop-based approach is O(n). This is more efficient as compared to the recursive approach.

4. Download the source code

Download
You can download the full source code of this example here: Fibonacci Java Example

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

 

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

 

and many more ....

 

Receive Java & Developer job alerts in your Area

 

Leave a Reply

avatar

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
Notify of