10

私はプログラミングの本を読んでいますが、例の1つはフィボナッチ数に関するものであり、繰り返し関数がn番目のフィボナッチ数を見つける方法です。

コードは次のようになります。

Int fib (int n)
{
If (n<3)
Return (1);
Else
Return (fib(n-1))+(fib(n-2))
}

電話から入力していて、コードがどのように機能しているかを理解しているため、これは正確ではありません。1が返されるまで自分自身を呼び出し、その後、位置の正しいフィボナッチ数が得られるまで戻り値を合計します。順番に。

だから私はコードの助けを必要としない。私が助けを必要としているのは、なぜこれが機能するのかを理解することです。すべての返品を追加すると、どのように正しい答えが得られますか？

なぜこれが機能しているのか誰かに説明してもらえますか？ありがとう。それは私を怒らせています。

4

9 に答える 9

13

再帰は次のようになります。

  1. 子供が眠れなかったので、母親は彼女に小さなカエルの話をしました、
  2. 眠れなかったので、カエルの母親は彼女に小さなクマの話をしました、
  3. 眠れなかったので、クマの母親は彼女に小さなイタチについての話をしました...
  4. 眠りに落ちた人。
  5. ..そして小さなクマは眠りに落ちました。
  6. ...そして小さなカエルは眠りに落ちました。
  7. ...そして子供は眠りに落ちました。

ソース

于 2010-11-04T00:00:36.297 に答える
9

再帰がどのように機能するかを理解することをお勧めします。基本的に、fib関数は、引数が2になるまで小さい引数でそれ自体を実行し、その後は1を返します。

fib(1) = 1
fib(2) = 1
fib(3) = fib(2) + fib(1) = 1 + 1 = 2
fib(4) = fib(3) [ fib(2) + fib(1) = 1 + 1 = 2 ] + fib(2) = 2 + 1
...

それがどのように機能するかを理解する1つの方法は、デバッガーで段階的に実行することです。

于 2010-11-03T23:57:38.540 に答える
5

フィボナッチ数は、先行する2つのフィボナッチ数の合計として定義されます。これにより、次のようになります。

1 1 2 3 5 8 13 ...

したがって、3番目の数（1 1 2）の場合、前の数、つまり2番目の（1 1 2）数を見つけて、前の数の前の数、つまり1番目（1 1 2）の数に追加します。

また、プログラムが知りたい数値を計算する前に、先行する2つの数値の値を計算する必要があることも理解する必要があります。したがって、すべてを計算するまで、同じメソッドを使用して自分自身を呼び出し続けます。

于 2010-11-03T23:59:02.717 に答える
5

それはフィボナッチ数の定義です。

n番目のフィボナッチ数は（n-1）番目と（n-2）番目のフィボナッチ数の合計を返します。

したがって、帰納的推論により、fib（n-1）およびfib（n-2）が有効な（n-1）番目および（n-2）番目のフィボナッチ数を与える場合、fib（n）= fib （n-1）+ fib（n-2）は、有効なn番目のフィボナッチ数になります。

基本的なステップは、fib（1）とfib（2）が正しいことです（つまり、fib（1）= fib（2）= 1）...

于 2010-11-04T00:02:02.193 に答える
3

再帰を理解する秘訣は、スタックを理解することです。

私は2行目で、という関数を使用しmainています。すべてのローカル変数はスタックフレームに格納されています。

+------------------+
| main() variables | The stack frame
+------------------+

次に、を呼び出すとfib(3)、コンピューターは現在の位置（EIP）をスタックにプッシュし、fib用の新しいスタックフレームを作成して追加します。一番上のスタックフレームにしかアクセスできません。

+------------------+
| fib()  n = 5     | Top of stack (current frame)
+------------------+
| EIP: main @ 2,1  |
+------------------+
| main() variables | Bottom of stack
+------------------+

の4行目では、再度fib呼び出さfibれるため、同じことが再び発生します。

+------------------+
| fib()    n = 4   | Top of stack
+------------------+
| EIP: fib @ 4,1   |
+------------------+
| fib()    n = 5   |
+------------------+
| EIP: main @ 2,1  |
+------------------+
| main() variables | Bottom of stack
+------------------+

そして、関数が再帰的に呼び出されるときに、これを何度も繰り返します。スタックは何かが戻るまで成長し、その時点で、の2行目でfib1を返します。これにより、一番上のスタックフレームがポップされて破棄され、保存された実行ポインタに実行が返され、プログラムは中断したところから続行します。

+------------------+
| fib()    n = 3   | Top of stack
+------------------+
    ... etc ...
+------------------+
| EIP: main @ 2,1  |
+------------------+
| main() variables | Bottom of stack
+------------------+

最終的には、呼び出し元の関数に戻ります（または、スタックが大きくなりすぎると、スタックオーバーフローが発生します）。覚えておくべき重要なことは、関数が呼び出されるたびに、すべてのローカル変数を含む新しいスタックフレームが取得され、以前の位置が保存されることです。それが再帰です。

主な問題は、人々に再帰を教える際に、誰もが常にフィボナッチ数列を使用することです。これは、1行に2つの再帰関数呼び出しがあることを意味します。あなたが同意すると確信しているので、これは不必要に混乱します！

于 2010-11-04T00:26:04.567 に答える
2

フィボナッチ数は、前の2つのフィボナッチ数の合計として定義されます。これはそれぞれ、前の2つのフィボナッチ数の合計として定義されます。Etceteraなど、1に到達するまで。わかりますか？任意のランダムなフィボナッチ数は、2つのフィボナッチ数の合計として定義できます。これらは、2つのフィボナッチ数の合計などとして再帰的に定義できます。つまり、フィボナッチ数の定義は基本的に再帰的です。つまり、その定義には、それが定義するものが含まれます。

これは難しい場合がありますが、再帰とコンピュータサイエンスを理解するための非常に基本的なことです。それに取り組んでください。最終的にクリックします。

于 2010-11-03T23:57:14.730 に答える
1

このビデオチュートリアルでは、フィボナッチ再帰がどのように機能するかをよりよく理解できるはずです。

[リンク] http://www.schooltrainer.com/study-material/computer-science/stepping-through-recursive-fibonacci-function.html

于 2011-11-14T20:07:37.417 に答える
1

それは再帰と呼ばれます

于 2010-11-03T23:57:26.573 に答える
0

定義上、フィボナッチ数は、シリーズの前の2つの数の合計です（最初の2つは0と1です）。

したがって、1つの場所でフィボナッチ数を取得すると、以前の2つのフィボナッチ数の合計として書き直すことができます。

再帰を使用して、「以前の2つのフィボナッチ数」が1と1になるまでこのプロセスを実行し（このアルゴリズムの場合）、次に、に戻るまで再帰を「バックアップ」します。シーケンス内の元の場所。

于 2010-11-04T00:01:39.210 に答える