Core Java

Fibonacci Java Example

In this article, we are going to explain the Fibonacci sequence in Java. We will see 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,

fibonacci numbers

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

In this article, we explained the Fibonacci sequence in Java through examples.

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

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.
Subscribe
Notify of
guest

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

0 Comments
Inline Feedbacks
View all comments
Back to top button