8

Python での次の基本的な再帰を考えてみましょう。

def fibonacci(number):
    if number == 0: return 0
    elif number == 1:
        return 1
    else:
        return fibonacci(number-1) + fibonacci(number-2)

フィボナッチ数列の (n-1) + (n-2) 関数によると、これは理にかなっています。

Pythonは、同じコード行内ではなく内部に別の再帰を含む再帰をどのように実行しますか? 「finobacci(number-1)」は「1」に達するまですべての再帰を完了し、「fibonacci(number-2)」で同じことを行ってそれらを追加しますか?

比較のために、数値 'x' を累乗 'y' にする次の再帰関数を見てみましょう。1 行に 1 つの再帰呼び出ししかないため、再帰を理解できます。y==0 の場合、最後に実行されたコマンドが「return 1」であるため、すべての結果が「1」であってはならないので、x は返されませんか?

def power(x, y):
    if y == 0:
        return 1
    else:
        return x*power(x, y-1)
4

10 に答える 10

16

簡潔な答え

Python が "見る" たびfibonacci()に、別の関数呼び出しが行われ、その関数呼び出しが完了するまで先に進みません。

例

では、 を評価しているとしましょうfibonacci(4)。

回線return fibonacci(number-1) + fibonacci(number-2)に到達すると、コールを「認識」しますfibonacci(number-1)。

これで実行されますが、まだまったくfibonacci(3)表示fibonacci(number-2)されていません。実行するfibonacci(3)には、把握する必要がありfibonacci(2)+fibonacci(1)ます。繰り返しますが、最初に見つけた関数を実行しますが、今回はfibonacci(2)です。

が実行されると、最終的に基本ケースに到達しfibonacci(2)ます。を評価fibonacci(1)して を返し1、初めて呼び出しの+ fibonacci(number-2)部分に進むことができfibonacci()ます。fibonacci(0)を返し0、次にfibonacci(2)returnを許可します1。

fibonacci(3)から返された値を取得したので、評価( )fibonacci(2)に進むことができます。fibonacci(number-2)fibonacci(1)

このプロセスは、すべてが評価されてfibonacci(4)返されるまで続きます3。

評価全体がどのように進行するかを確認するには、次の図の矢印に従ってください。

ここに画像の説明を入力してください

于 2012-12-04T17:40:16.587 に答える
10

式fibonacci(number-1) + fibonacci(number-2)では、2 番目の関数呼び出しが呼び出される前に、最初の関数呼び出しが完了する必要があります。

したがって、2 番目の呼び出しが開始される前に、最初の呼び出しの再帰スタック全体が完了する必要があります。

于 2012-12-04T17:38:56.213 に答える
5

'finobacci(number-1)' は '1' に達するまですべての再帰を完了し、'fibonacci(number-2)' で同じことを行い、それらを追加しますか?

はい、その通りです。つまり、次の

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

と同等です

f1 = fibonacci(number-1)
f2 = fibonacci(number-2)
return f1 + f2
于 2012-12-04T17:41:06.213 に答える
3

rcvizモジュールを使用して、再帰関数にデコレータを追加するだけで再帰を視覚化できます。

上記のコードの視覚化は次のとおりです。

rcviz を使用した OP の関数の出力

エッジには、実行によってトラバースされた順序で番号が付けられます。エッジは黒から灰色にフェードアウトし、トラバーサルの順序を示します。黒のエッジが最初で、グレーのエッジが最後です。

( GitHubで rcviz モジュールを作成しました。)

于 2014-04-28T22:51:57.540 に答える
2

コードをPython tutorに入れることを強くお勧めします。

あなたはその場でそれを手に入れることができるでしょう。スタックフレーム、リファレンスなどを参照してください。

于 2012-12-04T17:43:27.593 に答える
0

2 番目の再帰関数はこれを行うため (例)、1 は返されません。

power(2, 3)

2 * power(2, 2)

2 * 2 * power(1,2)

2 * 2 * 2 * power(0,2) # Reaching base case

2 * 2 * 2 * 1

8
于 2012-12-04T17:43:01.637 に答える
0

関数に print 関数を入れて深さを追加することで、これを自分で理解できます。これにより、よりきれいに印刷できます。

def fibonacci(number, depth = 0):
    print " " * depth, number
    if number == 0:
        return 0
    elif number == 1:
        return 1
    else:
        return fibonacci(number-1, depth + 1) + fibonacci(number-2, depth + 1)

呼び出しfibonacci(5)により、次のことが得られます。

5
 4
  3
   2
    1
    0
   1
  2
   1
   0
 3
  2
   1
   0
  1

5を呼び出し4て完了に進み、次に を呼び出して完了に進むことがわかります3。

于 2012-12-04T17:43:53.477 に答える
0

Matthew と MArtjin は正しいが、私は詳しく説明するかもしれないと思った:

Python は可能な限り左から右に処理します。この規則の例外は、括弧で示されています。

in x*power(x, y-1):x評価されてからpower評価される

にある間、fibonacci(number-1) + fibonacci(number-2)評価fibonacci(number-1)され（再帰的に、停止するまで）、次にfibonacci(number-1)評価されます

于 2012-12-04T17:44:12.173 に答える