Python で効率的な合計を行うために末尾呼び出し再帰を実装するにはどうすればよいですか?

Python の再帰: 理解するためのガイド

整数のリストを合計するための再帰関数

という再帰関数を作成する必要があるとします。リスト内のすべての整数の合計を計算する「listSum」。目標は、組み込み関数を使用せずにこれを行うことです。まず、関数の結果をそれ自体で表現する方法を考えます。

この場合、同じ関数を呼び出した結果に最初の数値を加算することで結果を取得できます。リスト内の残りの要素。再帰的に、これは次のように表現できます:

listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6])
                         = 1 + (3 + listSum([4, 5, 6]))
                         = 1 + (3 + (4 + listSum([5, 6])))
                         = 1 + (3 + (4 + (5 + listSum([6]))))
                         = 1 + (3 + (4 + (5 + (6 + listSum([])))))

再帰の基本ケースは、リストが空になるとき、つまり結果 0 を必要とするイベントです。このアプローチを Python コードで実装します:

<code class="python">def listSum(ls):
    if not ls:
        return 0
    return ls[0] + listSum(ls[1:])</code>

末尾呼び出し再帰

以前の実装は、実際の結果を計算するために前の関数呼び出しの値に依存しています。これは、末尾呼び出し再帰を使用して改善できます。

<code class="python">def listSum(ls, result):
    if not ls:
        return result
    return listSum(ls[1:], result + ls[0])</code>

追加のパラメーター結果を導入することで、その中に合計が蓄積され、基本条件が満たされたときにそれが返されます。

Passing Around Index

複数の中間リストの作成を避けるために、処理対象の項目のインデックスを渡すことができます。

<code class="python">def listSum(ls, index, result):
    if index == len(ls):
        return result
    return listSum(ls, index + 1, result + ls[index])</code>

基本条件は、インデックスがリストの長さに達したかどうかをチェックします。

内部関数のバージョン

パラメータの受け渡しを簡略化するために、内部関数を使用できます。

<code class="python">def listSum(ls):
    def recursion(index, result):
        if index == len(ls):
            return result
        return recursion(index + 1, result + ls[index])
    return recursion(0, 0)</code>

内部関数の再帰はインデックスと結果のパラメータを受け取り、listSum が返します。初期値を使用して内部関数を呼び出した結果。

デフォルト パラメータのバージョン

デフォルト パラメータを使用すると、さらに簡素化されます。

<code class="python">def listSum(ls, index=0, result=0):
    if index == len(ls):
        return result
    return listSum(ls, index + 1, result + ls[index])</code>

デフォルト値はインデックスと

再帰累乗問題

累乗(基数, 指数)を計算する問題を考えてみましょう。これは、基数を指数で累乗した値を返します。再帰的に、解を定義できます:

power(2, 5) = 2 * power(2, 4)
            = 2 * (2 * power(2, 3))
            = 2 * (2 * (2 * power(2, 2)))
            = 2 * (2 * (2 * (2 * power(2, 1))))

基本条件は指数が 1 以下になるときです。この場合、結果は基本そのものになります:

            = 2 * (2 * (2 * (2 * 2)))
            = 2 * (2 * (2 * 4))
            = 2 * (2 * 8)
            = 2 * 16
            = 32

Python での実装:

<code class="python">def power(base, exponent):
    if exponent <= 1:
        return base
    return base * power(base, exponent - 1)</code>

テールコール最適化バージョンのデフォルトパラメータの使用:

<code class="python">def power(base, exponent, result=1):
    if exponent <= 0:
        return result
    return power(base, exponent - 1, result * base)</code>

以上がPython で効率的な合計を行うために末尾呼び出し再帰を実装するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。