[解決済み] Java再帰的フィボナッチ数列

質問

この簡単なコードについて説明してください。

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

特に最後の行で混乱しています。例えば n = 5 ならば fibonacci(4) + fibonacci(3) が呼ばれ、以下同様ですが、このアルゴリズムがこの方法でインデックス 5 の値を計算するのかが理解できないのです。詳しい説明をお願いします。

どのように解決するのですか？

フィボナッチ数列では、各項目は前の2つの和になります。そこで、再帰的なアルゴリズムを書きました。

だから

fibonacci(5) = fibonacci(4) + fibonacci(3)

fibonacci(3) = fibonacci(2) + fibonacci(1)

fibonacci(4) = fibonacci(3) + fibonacci(2)

fibonacci(2) = fibonacci(1) + fibonacci(0)

今、あなたはすでに知っている fibonacci(1)==1 and fibonacci(0) == 0 . そこで、続いて他の値を計算することができます。

では

fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5

そしてフィボナッチ数列から 0,1,1,2,3,5,8,13,21.... について、以下のことがわかります。 5th element フィボナッチ数列が返す 5 .

についてはこちらをご覧ください。 再帰チュートリアル .