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 "", line 1, in  File "", line 4, in fact ... File "", line 4, in fact RuntimeError: maximum recursion depth exceeded in comparison

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