Fibonacci Recursion- Java program to Generate Fibonacci Series

by

In this Java tutorial, you’ll learn to generate Fibonacci Series using Recursion in Java. We’ll learn to develop a complete Java program to generate the Fibonacci series with Recursion mechanism. So let’s get started–

Learn - What is the Fibonacci sequence and How to print using Recursion in Java

What is Fibonacci Series?

In Fibonacci series, each and every number is the sum of its previous two numbers. The Fibonacci series always starts from 0 and 1, so the next number of the Fibonacci series would be the sum of 0 and 1 i.e. 0+1 == 2

Here is the Fibonacci series of the First 10 numbers –

Generating Fibonacci series -- 
0  1  2  3  5  8  13  21  34  55 . . .

Fibonacci ~ Recursion ~ Java

Now, you know What is Fibonacci series. You can generate the above Fibonacci series in Java with a number of methods. One of the popular methods to Generate Fibonacci series is by using Recursion in Java.

What is Fibonacci sequence - Wikipedia
Image Src : Wikipedia

Short note on Recursion –

  • Recursion is a technique to solve a problem in self – similar manner.
  • Technically speaking, a method or function that calls itself is known as Recursive method.
  • The process of a method to call itself, again and again, is known as Recursion.

Steps to Generate Fibonacci with Recursion

You can generate Fibonacci series using Recursion. In Java programming, we can also make use of loops like for(){…} loop or while(){…}, but first let’s understand the steps of generating Fibonacci sequences –

[Step 1] Set the Range and Exit case

[Step 2] Pass it to the method

[Step 3] The method calls itself passing lesser values

[Step 4] Methods terminate at the Exit cases

[Step 5] Verify the generated Fibonacci series

Let’s implement the above steps to understand better and Generate the series –

Example 1: Fibonacci series with Recursion in Java

Below is the Java program to print the Number placed at the given position in the Fibonacci series (using Recursion) –

package com.shubhamklogic.java.tutorials;

public class FibonacciExample {                                          // Explaining Step-by-Step

    public static void main( String[] args ) {
    
        long position = 5;                                               // Setting- which number is there in Fib. Series at this position?
        
        System.out.println("The Number in Fibonacci Series at "+ position + "th position - ");

        System.out.print( fibonacci( position ) + "  ");                 // Calling to get the num.
    }
    public static long fibonacci(long n) 
    {
        if (n == 0)                                                      // 1st Exit case...
            return 0;
        else if (n == 1)                                                 // 2nd Exit case...
            return 1;
        else
            return fibonacci(n - 1) + fibonacci(n - 2);                  // Calling itself recursively...
    } 
}

 

Output: When you will run the above program, you’ll successfully get the below result-

The Number in Fibonacci Series at 5th position-
3

The Fibonacci series of the first 5 elements would be like – 0 1 1 2 3 and we have got the correct results as at 5th position, number 3 gets the place.

However, by using the above program, you can also generate a complete Fibonacci series by calling the method after wrapping it within a loop. But, to do it in a Recursive manner, Here is how you can do it-

Example 2: Fibonacci series using Recursion in Java

We can generate a Fibonacci series by doing a simple mathematical calculation. In Fibonacci series, to get the next number, we would have to add the previous two numbers, and we need to keep doing that until we touch the limit.

Here is a simple program to print Fibonacci series of n numbers in Java :

package com.shubhamklogic.java.tutorials;

public class FibonacciExample                                     //Body of the class
{
    static int firstNum = 0, secondNum = 1, nextNum;              // Setting the first two numbers with 0 and 1

    public static void generateFibonacci(int limit) 
    {
        if (limit > 0) {
            nextNum = firstNum + secondNum;                       // Calculating the next number of the series
            firstNum = secondNum;                                 // Updating the values of previous variables
            secondNum = nextNum;
            
            System.out.print(" " + nextNum);      
            generateFibonacci(limit - 1);                         // Method generateFibonacci() is calling to itself- "Recursion"
        }
    }
    public static void main(String args[]) {
        int limit = 5;                                            // The limit...
        System.out.print(firstNum + "  " + secondNum);            // Printing the first two numbers which are 0 and 1
        generateFibonacci(limit - 2);                             // Passing limit-2 or 5-2 or 3  because 2 numbers are already printed
    }
}

 

 

Output: Once you’ll run the above code, you’ll successfully generate a Fibonacci series of first 5 numbers using Recursion in Java –

0 1 1 2 3

Logic : Behind the code

If you want to see what is happening behind the code, here is method calling, execution and result generation of above Fibonacci – Recursion – Java program :

Input number          :   5
Methods call stack    :   How does Fibonacci Recursion work?

Output Screen                          Methods calling to next one
-------------------+-----------------------------------------------------------------------------------
                                       main()
0  1                                   generateFibonacci( 5-2 )     OR      generateFibonacci( 3 )
0  1  1                                generateFibonacci( 3-1 )     OR      generateFibonacci( 2 )
0  1  1  2                             generateFibonacci( 2-1 )     OR      generateFibonacci( 1 )
0  1  1  2  3                          generateFibonacci( 1-1 )     OR      generateFibonacci( 0 )
-------------------+------------------------------------------------------------------------------------

In the above methods’ call stack, you can easily understand that-

  • Recursion is started from the main( ) method.
  • At first call, the generateFibonacci(…) method gets the number 5-2 i.e. 3
  • And then, it’s calling to itself by passing its reduced value.
  • At the same time in output screen, we are getting the sequences of Fibonacci series.
  • The method generateFibonacci(…) gets terminated after getting 1-1 == 0
  • That’s how we generate a Fibonacci series using recursion in Java.

Wrap Up 

In this Java tutorial, we learned- What is the Fibonacci sequence? Fibonacci sequence formula, and Step of Fibonacci algorithm. We also traced- Which method is calling to which one.

I hope this article helped you to understand- How to develop a Java program to Generate Fibonacci sequences using recursion. If you have any doubt, do comment below.

And, Don’t forget to check other related Java articles that you may like –

Read Next :

Leave a Comment