コードは次のとおりです。
class qual
{
public static int fibonacci(int n)
{
if (n == 0 || n == 1)
{
return 1;
}
else
{
return fibonacci(n-1) + fibonacci(n-2);
}
}
public static void main(String[] arg)
{
System.out.println(fibonacci(5));
}
}出力は8でした。出力は8であるはずですが、これを見ると7（(5-1) +(5-2)）であると思います。
なぜ出力8だったのですか？8を取得する理由は、再帰が私を混乱させるのをやめるかもしれないと思います。
これを代数のように扱いましょう。スペースを節約するf(n)代わりに、次のように記述します。fibonacci(n)
f(5) = f(4) + f(3)
f(5) = f(3) + f(2) + f(2) + f(1)
f(5) = f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
f(5) = f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
f(5) = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
これは再帰呼び出しであるため、引数が0または1でない各呼び出しは、それを再度呼び出します。
fibonacci(7)
-> fibonacci(6) // recursively calls itself with (7-1)
-> fibonacci(5) // recursively calls itself with (6-1)
-> fibonacci(4) // recursively calls itself with (5-1)
-> fibonacci(3) // recursively calls itself with (4-1)
-> fibonacci(2) // recursively calls itself with (3-1)
-> fibonacci(1) // recursively calls itself with (2-1)
-> fibonacci(4) // recursively calls itself with (6-2)
...
-> fibonacci(5) // recursively calls itself with (7-2)
-> fibonacci(4) // recursively calls itself with (5-1)
-> fibonacci(3) // recursively calls itself with (4-1)
-> fibonacci(2) // recursively calls itself with (3-1)
-> fibonacci(1) // recursively calls itself with (2-1)
-> fibonacci(3) // recursively calls itself with (5-2)
...
等々。
このようなロジックについて考えてみてください。そうすれば、最初の呼び出し元に実際に何が返されるかを理解できるはずです。
fibonacci(n-1)ではなく、戻ってきn-1ます。これを5で呼び出すと、次のようになります。
return fib(4) + fib(3);
fib（4）は以下を返します：
return fib(3) + fib(2);
fib（3）は以下を返します：
return fib(2) + fib(1);
fib（2）は以下を返します：
return fib(1) + fib(0);
fib（1）またはfib（0）に到達するとすぐに、1を返します。
逆方向に作業して、fib(2)2を返します。
return 1 /*fib(1)*/ + 1 /*fib(0)*/;
同じ論理で、、または3 をfib(3)返します。または5 を返します。そのため、8を返します。2 + 1Fib(4)3 + 2Fib(5)5 + 3
おそらく、コンピュータプログラムの構造と解釈（SICP、またはウィザードブック）から採用されたこの図は、次のことに役立ちます。
SICPは、プログラミングの入門が難しい場合もありますが、非常に深いものです。教育言語としてLisp（むしろScheme）を使用しているため、再帰が全体で使用されます。Lispの反復プロセスでさえ、再帰呼び出しに基づいています。
(define (factorial n)
(define (fact-iter n product)
(if (> n 1)
(fact-iter (- n 1) (* product n))
product
) )
(fact-iter n 1)
)
(factorial 5)
; returns 120
実際には反復的です。注：carリストの先頭をcdr返し、末尾を返します。演算子はプレフィックス表記を使用します; (- a b)は「a--b」、(* a b)は「a*b」です。
スキームでのフィボナッチプログラムは次のようになります。
(define (fibonacci n)
(if (or (= n 1) (= n 2))
1
(+ (fibonacci (- n 1)) (fibonacci (- n 2)))
)
それは((5-1) + (5-2))ではなく、むしろ(finonacci(5-1) + fibonacci(5-2))
そしてfinonacci(5-1)、に還元され、、などfibonacci(4)になります。(finonacci(4-1) + fibonacci(4-2))
return fibonacci (n-1) + fibonacci (n-2);
これは実際には（n-1）+（n-2）を実行しているだけでなく、フィボナッチ関数を再帰的に再度呼び出しています。
つまり、フィボナッチ（4）+フィボナッチ（3）を実行しています。そのfib（4）はfib（3）+ fib（2）であると評価されるため、最終的にfib（3）+ fib（2）+ fib（3）が返されます。繰り返しますが、これらのfib（3）のそれぞれは、実際にはfib（2）+ fib（1）というようになります。それが当たるまで、それはそのように壊れ続けます
if (n == 0 || n == 1)
つまり、最終的にはfib（1）+ fib（0）+ fib（1）...の束になります。これは1 + 1 + 1 ...であり、実際にすべてを壊すと8になります。ずっと下に。
私はまだこのアプローチを見ていません。結果を保存して構築していると想像してください。ここf[i]で、を呼び出した結果ですfibonacci(i)。0と1は基本ケースであり、残りはそれに基づいています。
f[0] = 1
f[1] = 1
f[2] = f[1] + f[0] = 1 + 1 = 2
f[3] = f[2] + f[1] = 2 + 1 = 3
f[4] = f[3] + f[2] = 3 + 2 = 5
f[5] = f[4] + f[3] = 5 + 3 = 8
再帰は、実際には帰納法による証明の数学的概念と密接に関連しています。実際、フィボナッチ数列は再帰的に定義されているため、あるレベルでは、それがどのように機能するかを理解するために、すでに再帰的に考える必要があります。
コードをよりよく理解するために、ベータ削減を適用できます。つまり、各関数呼び出しを関数自体の本体に置き換えます。
その場合、次のようにfibonacci(n)変換されfibonacci(n - 1) + fibonacci(n - 2)ます。
fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(5) = (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
特別なケースを作らない限り、これが永遠に続くことは容易に理解できます。fibonacci(1)ここで、それはに変換され1、fibonacci(0)またに変換されることがわかり1ます。したがって、残りがすべてになるまでベータ削減を続けます。これは次のようになります。
fibonacci(5) = ((1 + 1) + (1 + (1 + 1))) + ((1 + 1) + 1)
したがって：
fibonacci(5) = 8
関数の結果は、ではなく(5 - 1) + (5 - 2)、fibonacci( 5 - 1 ) + fibonacci( 5 - 2 )またはfibonacci( 4 ) + fibonacci( 3 )、5+3です。シーケンスは次のとおりです。
1 1 2 3 5 8
0 1 2 3 4 5
最初のフィボナッチ数は1,1,2,3,5,8、...他の数は予想外です。