python - たくさんの関数呼び出しを取り除く方法は?

Question

たくさんの関数呼び出しを取り除く方法は? 再帰関数の例を次に示します。

def factorial(n):
    if n <= 1:
      return 1
    else:
      return n * factorial(n - 1)

デコレータで簡単にできると聞いたのですが使い方がわかりません

Answer 1

アルゴリズムを注意深く調べ、冗長な呼び出しを排除したと仮定すると、反復的な方法で (つまり、再帰ではなくループを使用して) 関数を書き直すことができます。

多くの場合、再帰は問題の解決策を適切に表現できますが、かなりメモリを消費し (スタックに状態を繰り返し保存する)、すべての関数呼び出しのためにそれほど高速ではありません。その主な利点は表現力にあります。

メモ化は別のオプションであるため、再計算 (関数の呼び出し) を行うのではなく、まず値を既に計算 (および保存) したことがあるかどうかを確認し、代わりにそれを使用します。

Answer 2

末尾呼び出しの最適化を探しています。これは基本的に、再帰プログラムを書き換えずに反復プログラムに変換する手法です。たとえば、階乗関数を n = 1000 で呼び出すと、Python は「最大再帰深度を超えました」というエラーを出して失敗します。ただし、関数を末尾再帰に書き換えると、次のようになります。

def tail_factorial(n, result=1):
    if n <= 1:
        return result
    else:
        return fac(n - 1, result * n)

次に、「トランポリン」を使用して呼び出します。

def trampoline_factorial(n):

    def fac(n, result=1):
        if n <= 1:
            return result
        else:
            return lambda: fac(n - 1, result * n)

    f = fac(n)
    while callable(f):
        f = f()
    return f

あなたは1000を評価することができます！問題なく。

テイルコールの最適化は、デコレーターを使用して Python で実際に自動化できます。たとえば、こちらを参照してください。