How to Generate Recursive Fibonacci Sequence in Java

1. Fibonacci Sequence
2. Recursion
3. Recursive Fibonacci Sequence in Java

Fibonacci Sequence

A sequence that is formed by the addition of the last two numbers starting from 0 and 1. If one wants to find the nth element, then the number is found by the addition of (n-1) and (n-2) terms, where n must be greater than 0.

Recursion

Recursion is the process where the same definitive function or procedure calls itself multiple times until it encounters a terminating condition. If we do not specify a terminating condition, the method will enter into an infinite loop state.

Recursive Fibonacci Sequence in Java

In the code given below, the main() method calls a static function getFibonacciNumberAt() defined in the class. The function takes a parameter that defines a number, where we want to evaluate the Fibonacci number. The function has a primary check that will return 0 or 1 when it meets the desired condition. Otherwise, the function will again call itself by decrementing the parameter passed to it.

package recursiveFibonacci;

public class RecursiveFibonacciSequence {
  public static void main(String[] args) {
    int fibonacciNumber = getFibonacciNumberAt(6);
    System.out.println(fibonacciNumber);
  }

  public static int getFibonacciNumberAt(int n) {
    if (n == 0)
      return 0;
    else if (n == 1)
      return 1;
    else
      return getFibonacciNumberAt(n - 1) + getFibonacciNumberAt(n - 2);
  }
}

Output:

8

The detailed evaluation can be seen below :

getFibonacciNumberAt(6) = getFibonacciNumberAt(5) + getFibonacciNumberAt(4); //5+3=8
getFibonacciNumberAt(5) = getFibonacciNumberAt(4) + getFibonacciNumberAt(3); //3+2=5
getFibonacciNumberAt(4) = getFibonacciNumberAt(3) + getFibonacciNumberAt(2); //2+1=3
getFibonacciNumberAt(3) = getFibonacciNumberAt(2) + getFibonacciNumberAt(1); //1+1=2
getFibonacciNumberAt(2) = getFibonacciNumberAt(1) + getFibonacciNumberAt(0); //1+0=1
If, getFibonacciNumberAt(1) = 1;
And getFibonacciNumberAt(0) = 0;

We can modify the above program to print a series up to the desired number.

package recursiveFibonacci;

public class RecursiveFibonacci {
  public static void main(String[] args) {
    int maxCount = 10;
    for (int i = 0; i <= maxCount; i++) {
      int fibonacciNumber = printFibonacci(i);
      System.out.print(" " + fibonacciNumber);
    }
  }

  public static int printFibonacci(int n) {
    if (n == 0)
      return 0;
    else if (n == 1)
      return 1;
    else
      return printFibonacci(n - 1) + printFibonacci(n - 2);
  }
}

Output:

0 1 1 2 3 5 8 13 21 34 55