この簡単なコードを説明してください:
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 の値をどのように計算するのか理解できません。詳しく説明してください。
ベストアンサー1
フィボナッチ数列では、各項目は前の 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
こちらをご覧ください再帰チュートリアル。