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
Note

For calculation of larger numbers, we can use the BigInteger class in Java. The recursion process will be complex for larger numbers; hence the computation time for such numbers will also be more.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Java Math

  • Infinity in Java