Python 再帰

このチュートリアルでは、再帰関数 (自分自身を呼び出す関数) の作成方法を学習します。

再帰とは?

再帰とは、何かをそれ自体で定義するプロセスです。

物理的な世界の例は、2 つの平行なミラーを互いに向かい合わせに配置することです。それらの間にあるオブジェクトは再帰的に反映されます。

Python 再帰関数

Python では、関数が他の関数を呼び出すことができることがわかっています。関数が自分自身を呼び出すことさえ可能です。これらのタイプの構成は、再帰関数と呼ばれます。

次の図は、recurse という再帰関数の動作を示しています。 .

<図>

以下は、整数の階乗を見つける再帰関数の例です。

階乗は、1 からその数値までのすべての整数の積です。たとえば、6 の階乗 (6 と表示) は 1*2*3*4*5*6 =720 です。 .

再帰関数の例

def factorial(x):
    """This is a recursive function
    to find the factorial of an integer"""

    if x == 1:
        return 1
    else:
        return (x * factorial(x-1))


num = 3
print("The factorial of", num, "is", factorial(num))

出力

The factorial of 3 is 6

上記の例では、 factorial() 自身を呼び出すため、再帰関数です。

この関数を正の整数で呼び出すと、数値を減らして再帰的に自分自身を呼び出します。

各関数は、数値が 1 になるまで、その数値にその下の数値の階乗を掛けます。この再帰呼び出しは、次の手順で説明できます。

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

何が起こっているかの段階的なプロセスを示す画像を見てみましょう:

<図>

数が 1 に減少すると、再帰は終了します。これは基本条件と呼ばれます。

すべての再帰関数には、再帰を停止する基本条件が必要です。そうしないと、関数は自分自身を無限に呼び出します。

Python インタープリターは、再帰の深さを制限して無限再帰を回避し、スタックオーバーフローを引き起こします。

デフォルトでは、再帰の最大深度は 1000 です .制限を超えると、RecursionError になります。 .そのような条件の 1 つを見てみましょう。

def recursor():
    recursor()
recursor()

出力

Traceback (most recent call last):
  File "<string>", line 3, in <module>
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

再帰の利点

<オール>

再帰関数により、コードがすっきりとエレガントに見えます。

複雑なタスクは、再帰を使用してより単純なサブ問題に分解できます。

ネストされた反復を使用するよりも再帰を使用すると、シーケンスの生成が簡単になります。

再帰の欠点

<オール>

再帰の背後にあるロジックを理解するのが難しい場合があります。

再帰呼び出しは多くのメモリと時間を消費するため、費用がかかります (非効率的です)。

再帰関数はデバッグが難しい。

Python 関数の引数 Python 匿名/Lambda 関数

Python