Python での末尾再帰

1. Python での再帰
2. Python での末尾再帰
3. Python で末尾再帰関数を呼び出す
4. 末尾再帰関数の利点

今日のチュートリアルでは、再帰とその型を通して末尾再帰について学びます。 さらに、Python で末尾再帰を呼び出す方法も学び、それを使用する利点を探ります。

Python での再帰

コンピューター サイエンスでは、再帰とは、特定の条件が満たされるまで関数が本体でそれ自体を呼び出す問題解決方法です。

これは貴重な方法の 1つであり、実際の使用例が数多くあります。 ただし、いくつかの制限があり、それは空間と時間の複雑さです。 以下の再帰の例を見てみましょう。

コード例:

def factorial(n):
    if n == 1 or n == 0:
        return 1
    else:
        return n * factorial(n - 1)  # recursive call


num = 4

# In this case factorial is 4x3x2x1 = 24
print(f"The factorial of {num} is {factorial(num)}")

出力：

The factorial of 4 is 24

再帰はスタックを使用してローカル変数を保持し、再帰を実行するたびにそのサイズが増加し、スタック サイズは制限されます。 これが、開発者がいくつかの最適化されたソリューションについて考え始めた理由です。

小さい数にのみ適しています。 そのため、開発者は単純な再帰の最適化されたソリューションを思いつきました。それが Tail Recursion です。

再帰の種類

再帰関数に関しては、主に 2つのタイプがあります。

1. 先頭再帰
2. 末尾再帰

先頭再帰は、関数が最初に自分自身を呼び出す場合であり、末尾再帰は、関数が再帰の最後に自分自身を呼び出す場合です。

どちらにも利点と欠点がありますが、一般的に末尾再帰の方が効率的であると考えられています。 以下で詳しく理解しましょう。

Python での末尾再帰

Python の 末尾再帰 は、単純な再帰に対する最適化されたソリューションです。 スタック オーバーフロー エラーを発生させることなく、無制限の再帰を許可します。

しかし、末尾呼び出し再帰の詳細に入る前に、末尾呼び出し再帰の定義を理解しましょう。 call は関数の呼び出しを検討していることを意味し、tail は最後のことを意味します。 したがって、末尾再帰メソッドを呼び出すということは、関数が関数の最後から繰り返し自分自身を呼び出すことを意味します。

現在、ほとんどのプログラミング言語は末尾再帰的です。つまり、再帰関数を最適化しています。

Python で末尾再帰関数を呼び出す

Python で末尾再帰関数を呼び出す方法は 2つあります。 1つ目は return キーワードを使用する方法で、2つ目は yield キーワードを使用する方法です。

return キーワードを使用して末尾再帰関数を呼び出す

まず、return キーワードを使用して、関数から値を返すことができます。 ただし、このキーワードは関数をすぐに終了させるため、注意が必要です。

これは、関数を再度呼び出す必要がないことが確実な場合にのみ使用できることを意味します。 returnキーワードを使用すると、関数は最後に計算された値を返すことに注意してください。

末尾再帰関数を呼び出す最も一般的な方法です。 たとえば、以下のコード フェンスを参照してください。

コード例:

def trisum(n, csum):
    while True:  # Change recursion to a while loop
        if n == 0:
            return csum
        n, csum = n - 1, csum + n  # Update parameters instead of tail recursion


trisum(1000, 0)

出力：

500500

yield キーワードを使用して末尾再帰関数を呼び出す

末尾再帰関数を呼び出す別の方法は、yield キーワードを使用することです。 このキーワードを使用すると、関数を終了せずに関数から値を返すことができます。

関数を繰り返し呼び出して、毎回異なる値を返すことができます。 多数の値を返す必要がある関数に便利です。

yield キーワードを使用すると、関数は最後に計算された値を yield します。 末尾再帰関数を呼び出す方法としてはあまり一般的ではありませんが、場合によっては役立ちます。

コード例:

def lprint(a):
    if isinstance(a, list):
        for i in a:
            yield from lprint(i)
    else:
        yield a


b = [[1, [2, 3], 4], [5, 6, [7, 8, [9]]]]
for i in lprint(b):
    print(i)

出力：

1
2
3
4
5
6
7
8
9

末尾再帰関数の利点

末尾再帰関数は、関数の最後のステートメントが再帰関数の呼び出しである再帰関数の一種です。

この関数は、関数が再帰呼び出しの中間値を追跡する必要がないため、非末尾再帰関数よりも効率的です。

これにより、末尾再帰関数がより効率的になり、理解しやすくなります。 末尾再帰関数を使用すると、多くの利点があります。

1. 末尾再帰の主な利点の 1つは、最適化が容易になることです。 テール コールは関数内で最後に行われるため、コンパイラはこれをより簡単に最適化できます。 これは、末尾再帰関数が時間と空間の点でより効率的であることを意味します。
2. 末尾再帰のもう 1つの利点は、理解しやすいことです。 再帰呼び出しは関数内で最後に行われるため、何が起こっているのかを簡単に確認できます。 これにより、末尾再帰関数のデバッグと保守が容易になります。
3. 中間値を追跡する必要がないため、非末尾再帰関数よりも効率的です。
4. 関数呼び出しスタックは関数の最後で常に空であるため、推論が容易になります。 また、末尾再帰関数はより簡単に並列化できます。
5. それらを反復プログラムに簡単に変換でき、場合によってはより効率的になります。
6. 関数の実行を高速化し、メモリの使用量を減らすことができます。 また、正しいコードを書きやすくすることもできます。