8

私は本当に再帰がどのように機能するかについて頭を悩ませ、再帰アルゴリズムを理解しようとしています。たとえば、以下のコードは、5を入力すると120を返しますが、無知なのですが、理由がわかりません。

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

answer = int (raw_input('Enter some number: '))

print fact(answer)
4

4 に答える 4

26

実行をウォークスルーしましょう。

fact(5):
   5 is not 0, so fact(5) = 5 * fact(4)
   what is fact(4)?
fact(4):
   4 is not 0, so fact(4) = 4 * fact(3)
   what is fact(3)?
fact(3):
   3 is not 0, so fact(3) = 3 * fact(2)
   what is fact(2)?
fact(2):
   2 is not 0, so fact(2) = 2 * fact(1)
   what is fact(1)?
fact(1):
   1 is not 0, so fact(1) = 1 * fact(0)
   what is fact(0)?
fact(0):
   0 IS 0, so fact(0) is 1

次に、結果を収集しましょう。

fact(5) = 5* fact(4)

結果をfact（4）に置き換えます

fact(5) = 5 * 4 * fact(3)

結果をfact（3）に置き換えます

fact(5) = 5 * 4 * 3 * fact(2)

結果をfact（2）に置き換えます

fact(5) = 5 * 4 * 3 * 2 * fact(1)

結果をfact（1）に置き換えます

fact(5) = 5 * 4 * 3 * 2 * 1 * fact(0)

結果をfact（0）に置き換えます

fact(5) = 5 * 4 * 3 * 2 * 1 * 1 = 120

そして、あなたはそれを持っています。再帰とは、些細な（または「基本」）ケースに到達するまで、大きな問題を小さな問題として成功裏に見なすことによって、大きな問題を分解するプロセスです。

于 2012-07-27T18:52:34.400 に答える
11

問題を実行ステップに分解します。

fact(5)
| 5  * fact(4)
|| 5 * (4 * fact(3))
||| 5 * (4 * (3 * fact(2))
|||| 5 * (4 * (3 * (2 * fact(1))))
||||| 5 * (4 * (3 * (2 * (1 * fact(0)))))
|||||| 5 * 4 * 3 * 2 * 1 * 1
120

他の関数が呼び出すことができるのと同じように、関数は単に自分自身を呼び出します。ただし、この場合、関数が無限に再発しないように、関数には停止点が必要です（スタックオーバーフローが発生します）。あなたの場合、これはnが0の場合です（代わりにおそらく1になるはずです）。

于 2012-07-27T18:50:38.023 に答える
6

fact（）を呼び出すたびに、外部から呼び出されるか、それ自体で呼び出されるかにかかわらず、独自のローカル変数のセットを取得することに注意してください。

fact(1) has n of 5
   fact(2) has n of 4
      fact(3) has n of 3
         fact(4) has n of 2
            fact(5) has n on 1
               fact(6) has n of 0

最も深いもの（ここでfact(6)は最も深い）は、コールスタック内のそれらより上のレベルが終了する前に完全に計算されます。

それで

  • fact(6)1を返しますfact(5)（終了ケース）。
  • fact(5)fact(4)1を（1 * 1）に返します
  • fact(4)fact(3)2を（2 * 1）に返します
  • fact(3)fact(2)6を（3 * 2）に返します
  • fact(2)fact(1)24を（4 * 6）に返します
  • そして最後に、 fact(1)120（5 * 24）を呼び出し元に返します。
于 2012-07-27T18:56:18.130 に答える
3

再帰関数は、それ自体を呼び出し、評価が終了して結果が生成されるまで呼び出しを続ける関数です。上記の階乗関数の鍵は、return x * fact（x-1）です。

したがって、5を入力すると、5 * fact（5-1）* fact 4-1）....が実行され、0に到達してから1が返されます。したがって、5 * 4 * 3 *2*になります。 120である1。

スタックに変数を割り当て続けます。したがって、高すぎる数値を入力すると、スタックオーバーフロー例外が発生する可能性があります。再帰関数をforループに変換し、割り当てられたメモリをクリーンアップする末尾呼び出し最適化（TCO）と呼ばれるものを使用しない限り。

于 2012-07-27T18:48:59.407 に答える