3

return fibonacci( number-1 ) + fibonacci( number-2 )次のプログラムで何が行われるかを理解するのに問題があります。

import sys
def fibonacci( number ):
    if( number <= 2  ):
        return 1
    else:
        return fibonacci( number-1 ) + fibonacci( number-2 )

問題は、この行がどのように機能するか想像できないことです。

return fibonacci( number-1 ) + fibonacci( number-2 )

「フィボナッチ（番号-1）」と「フィボナッチ（番号-2）」の両方が同時に処理されていますか？または、「fibonacci（number-1）」が最初に処理され、次に2番目に処理されますか？

両方を処理すると最終的に「1」が返されることがわかります。したがって、最後に期待する結果は「1 +1」=「2」です。

計算の過程を詳しく説明していただければ幸いです。

これは非常に新しい質問だと思いますが、そのプロセスを実際に把握することはできません。

4

4 に答える 4

5

このようなことをしてみませんか：

>>> def fibonacci(number):
...     if number < 2:
...         return number
...     print "Number is currently %d, getting fibonacci(%d)" % (number, number - 1)
...     minus_one = fibonacci(number-1)
...     print "Number is currently %d, just got fibonacci(%d), now getting fibonacci(%d)" % (number, number - 1, number - 2)
...     minus_two = fibonacci(number-2)
...     print "Number is currently %d, returning %d + %d" % (number, minus_one, minus_two)
...     return minus_one + minus_two

そのため、電話をかけるとfibonacci次のようになります。

>>> fibonacci(4)
Number is currently 4, getting fibonacci(3)
Number is currently 3, getting fibonacci(2)
Number is currently 2, getting fibonacci(1)
Number is currently 2, just got fibonacci(1), now getting fibonacci(0)
Number is currently 2, returning 1 + 0
Number is currently 3, just got fibonacci(2), now getting fibonacci(1)
Number is currently 3, returning 1 + 1
Number is currently 4, just got fibonacci(3), now getting fibonacci(2)
Number is currently 2, getting fibonacci(1)
Number is currently 2, just got fibonacci(1), now getting fibonacci(0)
Number is currently 2, returning 1 + 0
Number is currently 4, returning 2 + 1
3

それはまだ複雑ですが、少なくとも今、あなたはあなたの数を計算するために関数が何をしているのかを見ることができます。

于 2012-06-24T21:01:10.123 に答える
3

「フィボナッチ（番号-1）」と「フィボナッチ（番号-2）」の両方が同時に処理されていますか？または、「fibonacci（number-1）」が最初に処理され、次に2番目に処理されますか？

それは重要ですか？

何が起こっているのかというと、関数が2回呼び出されているということです。1回は-1の値でnumber、もう1回は-2の値で、その値が関数の現在の「インスタンス」numberに渡されました。

あなたが電話するとしますfibonacci(3)。その行は最終的に次のようになります。

return fibonacci(2) + fibonacci(1)
于 2012-06-24T20:44:47.210 に答える
2

私はノーレン・ロイヤルティの答えがとても好きですが、それでも視覚化するのは少し難しいです。だから、少しいじくり回した後： ここに画像の説明を入力してください

...時間は左から右に流れ、エッジが重ならないように微調整します。再帰しない葉のノードはオレンジ色です。

于 2012-06-24T21:04:47.140 に答える
2

最初は再帰を理解するのに苦労したので、関数を試してみます。

ここで、fibonacci（4）と呼んでみましょう。

数が多いので、2つのpythonがこの行に移動します。

フィボナッチ（数値-1）+フィボナッチ（数値-2）を返す

したがって、評価を開始し、次のように呼び出します。

fibonacci（3）＃これはfibonacci（4-1）です

関数呼び出しに遭遇するたびに、それを実行する必要があります（いわば）。

だから今それはfibonacci（3）をしようとします、そしてそれは2より大きいので：

再びこの行に移動します：

フィボナッチ（数値-1）+フィボナッチ（数値-2）を返す

今では3で呼んでいたので、fibonacci（number-1）に到達すると、次のようになります。

fibonacci（2）＃これはfibonacci（3-1）です

numerは2に等しいので、この再帰呼び出しは1を返します。ここで、Pythonがfibonacci（2）の答えを知っていることを覚えて/想像する必要があります。

これで、fibonacci（2）に対する回答が得られたので、次の行を実行し続けます。

フィボナッチ（数値-1）+フィボナッチ（数値-2）を返す

具体的にはこれ：+フィボナッチ（数-2）

私たちはfibonacci（2）に立っているので、これはfibonacci（1）を実行し、これは1を返します。

つまり、戻ったときに、つまり、再帰的に関数を終了します。

なにが問題だったの？私たちがフィボナッチ（4）をしたとき、私たちはフィボナッチ（3）、フィボナッチ（2）、フィボナッチ（1）を知る必要がありました。

したがって、それがフィボナッチ（3）に再帰的に出て行くとき、フィボナッチ（2）とフィボナッチ（1）を知る必要があり、それを知っているので、今ではフィボナッチ（3）になります。

ここで、fibonacci（3）とfibonacci（2）を知る必要があるfibonacci（4）に戻り、両方を知っているので、両方の合計で何が返されるかを確認します。

明確であることを願っています。再帰を追跡するのは非常に困難ですが、練習することで改善されます。

呼び出しを（鉛筆で）書き留めて、関数呼び出しを追跡してみてください。呼び出している呼び出しと、呼び出しから得られる結果を書き留めてください。

この種の再帰では、「答えを探す」再帰のレベルが下がり、それらの答え（リターン）を取得すると、再び戻って未知の値に答えを与えることを忘れないでください。

于 2012-06-24T21:13:50.453 に答える