Java での再帰的フィボナッチ数列

1. フィボナッチ数列
2. 再帰
3. Java での再帰的フィボナッチ数列

フィボナッチ数列

0 と 1 から始まる最後の 2つの数値の加算によって形成されるシーケンス。n 番目の要素を検索する場合は、（n-1）と（n-2）の項を加算して数値を検索します。ここで、n は 0 より大きくなければなりません。

再帰

再帰とは、同じ決定的な関数またはプロシージャが、終了条件に遭遇するまで、それ自体を複数回呼び出すプロセスです。終了条件を指定しない場合、メソッドは無限ループ状態になります。

Java での再帰的フィボナッチ数列

以下のコードでは、main() メソッドがクラスで定義された静的関数 getFibonacciNumberAt() を呼び出します。この関数は、フィボナッチ数を評価する数を定義するパラメーターを取ります。この関数には、目的の条件を満たすと 0 または 1 を返すプライマリチェックがあります。それ以外の場合、関数は渡されたパラメーターをデクリメントすることにより、再び自身を呼び出します。

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

出力：

8

詳細な評価は以下に見ることができます：

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;

上記のプログラムを変更して、希望する数までのシリーズを出力できます。

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

出力：

0 1 1 2 3 5 8 13 21 34 55