Sequência de Fibonacci recursiva em Java

Sequência de Fibonacci

Uma sequência que é formada pela adição dos dois últimos números começando em 0 e 1. Se alguém quiser encontrar o enésimo elemento, então o número é encontrado pela adição dos termos (n-1) e (n-2), onde n deve ser maior que 0.

Recursão

Recursão é o processo em que a mesma função ou procedimento definitivo chama a si mesmo várias vezes até encontrar uma condição de término. Se não especificarmos uma condição de término, o método entrará em um estado de loop infinito.

Sequência de Fibonacci recursiva em Java

No código fornecido a seguir, o método main() chama uma função estática getFibonacciNumberAt() definida na classe. A função recebe um parâmetro que define um número, onde queremos avaliar o número de Fibonacci. A função tem uma verificação primária que retornará 0 ou 1 quando atender à condição desejada. Caso contrário, a função se chamará novamente diminuindo o parâmetro passado a ela.

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);
  }
}

Resultado:

8

A avaliação detalhada pode ser vista abaixo:

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;

Podemos modificar o programa acima para imprimir uma série até o número desejado.

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);
  }
}

Resultado:

0 1 1 2 3 5 8 13 21 34 55