Python の再帰アルゴリズムは難しいですか? Python の再帰関数の詳細な例

関数内で他の関数を呼び出すことができます。関数が内部的にそれ自体を呼び出す場合、その関数は 再帰関数です。

たとえば、階乗 n! = 1 x 2 x 3 x ... x n を計算してみましょう。これは関数 fat(n) で表され、次のようになります。

fact(n ) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fat(n-1) x n

したがって、fact(n) は次のようになります。 n x fat(n-1) の場合、n=1 のみが特別な処理を必要とします。

つまり、fact(n) は 再帰的な方法で書かれています:

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

上記は再帰関数です。

>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
933262154439441526816992388562667004907159682643816214685
92963895217599993229915608941463976156518286253697920827223
758251185210916864000000000000000000000000

fact(5) を計算すると、関数定義に従って次のように計算プロセスがわかります:

===> fat(5)
=== > 5 * 事実(4)
===> 5 * (4 * 事実(3))
===> 5 * (4 * (3 * 事実(2) ))
===> 5 * (4 * (3 * (2 * 事実(1))))
===> 5 * (4 * (3 * (2 * 1)) )
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
= ==> 120

再帰関数の利点は、定義が簡単でロジックが明確であることです。理論的には、すべての再帰関数をループ内に記述することができますが、ループのロジックは再帰ほど明確ではありません。

再帰関数を使用する場合は、スタック オーバーフローを防ぐように注意する必要があります。コンピュータでは、関数呼び出しはスタックのデータ構造を通じて実装されます。関数呼び出しが入力されるたびにスタック フレームがスタックに追加され、関数が返されるたびにスタック フレームがスタックから減算されます。スタックのサイズは無限ではないため、再帰呼び出しが多すぎるとスタック オーバーフローが発生します。事実(1000)を試すことができます:

>>> fact(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in fact
  ...
  File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded in comparison

以上がPython の再帰アルゴリズムは難しいですか? Python の再帰関数の詳細な例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。