1

再帰を末尾再帰に変換することは常に可能ですか?

次の Python 関数を末尾再帰関数に変換するのに苦労しています。

def BreakWords(glob):
  """Break a string of characters, glob, into a list of words.

  Args:
    glob: A string of characters to be broken into words if possible.

  Returns:
    List of words if glob can be broken down. List can be empty if glob is ''.
    None if no such break is possible.
  """
  # Base case.
  if len(glob) == 0:
    return []

  # Find a partition.
  for i in xrange(1, len(glob) + 1):
    left = glob[:i]
    if IsWord(left):
      right = glob[i:]
      remaining_words = BreakWords(right)
      if remaining_words is not None:
        return [left] + remaining_words

  return None
4

1 に答える 1

2

常にそうであるかどうかはわかりませんが、ほとんどの再帰関数は末尾再帰として実装できます。また、Tail Recursion は Tail Recursion 最適化とは異なります。

テール再帰と「通常の」再帰の違い

再帰関数には、次の 2 つの要素が必要です。

  1. 再帰呼び出し
  2. 戻り値のカウントを保持する場所。

「通常の」再帰関数は (2) をスタック フレームに保持します。

通常の再帰関数の戻り値は、次の 2 種類の値で構成されます。

  • その他の戻り値
  • owns 関数の計算結果

例を見てみましょう：

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

フレーム f(5) は、たとえば、それ自身の計算 (5) の結果と f(4) の値を「格納」します。factorial(5) を呼び出すと、スタック呼び出しが崩壊し始める直前に、次のようになります。

 [Stack_f(5): return 5 * [Stack_f(4): 4 * [Stack_f(3): 3 * ... [1[1]]

各スタックには、前述の値に加えて、関数のスコープ全体が格納されていることに注意してください。したがって、再帰関数 f のメモリ使用量は O(x) です。x は、再帰呼び出しの回数です。したがって、factorial(1) または factorial(2) を計算するために 1kb の RAM が必要な場合、factorial(100) を計算するには ~100k が必要です。

Tail Recursive 関数は、引数に (2) を入れます。

Tail Recursion では、パラメーターを使用して、各再帰フレームの部分計算の結果を次のフレームに渡します。階乗の例、Tail Recursive を見てみましょう:

def factorial(n):
    def tail_helper(n, acc):
        if n == 1 or n == 2: return acc
        return tail_helper(n-1, acc + n)
return tail_helper(n,0)

factorial(4) のフレームを見てみましょう:

[Stack f(4, 5): Stack f(3, 20): [Stack f(2,60): [Stack f(1, 120): 120]]]]

違いがわかりますか？「通常の」再帰呼び出しでは、戻り関数が再帰的に最終値を構成します。Tail Recursion では、基本ケース (最後に評価されたもの) のみを参照します。古い値を追跡する引数をaccumulatorと呼びます。

再帰テンプレート

通常の再帰関数は次のようになります。

def regular(n)
    base_case
    computation
    return (result of computation) combined with (regular(n towards base case))

Tail 再帰で変換するには、次のようにします。

  • アキュムレータを運ぶヘルパー関数を導入する
  • アキュムレータを基本ケースに設定して、メイン関数内でヘルパー関数を実行します。

見て：

def tail(n):
    def helper(n, accumulator):
        if n == base case:
            return accumulator
        computation
        accumulator = computation combined with accumulator
        return helper(n towards base case, accumulator)
    helper(n, base case)

あなたの例：

私はこのようなことをしました：

def BreakWords(glob):
    def helper(word, glob, acc_1, acc_2):
        if len(word) == 0 and len(glob) == 0:
            if not acc_1:
                return None
            return acc
        if len(word) == 0:
            word = glob.pop[0]
            acc_2 = 0

        if IsWord(word.substring[:acc_2]):
            acc_1.append(word[:acc_2])
            return helper(word[acc_2 + 1:], glob, acc_1, acc_2 + 1)

        return helper(word[acc_2 + 1:], glob, acc_1, acc_2 + 1)

    return helper("", glob, [], 0)

あなたが作成した for ステートメントを削除するために、2 つのアキュムレータを使用して再帰ヘルパー関数を実行しました。1 つは結果を保存するためのもので、もう 1 つは現在試行中の位置を保存するためのものです。

テールコールの最適化

テール コール スタックの非境界ケースには状態が格納されていないため、それほど重要ではありません。一部の言語/インタープリターは、古いスタックを新しいスタックに置き換えます。そのため、呼び出しの数を制限するスタック フレームがないため、Tail Calls は for-loop のように動作します。

残念ながら、Python はこれらのケースの 1 つではありません。スタックが 1000 を超えると、RunTimeError が発生します。Guido氏 は、テイル コールの最適化 (フレームのスローによって引き起こされる) が原因で、デバッグ目的で失われた明確さが機能よりも重要であると考えています。残念です。Python には非常に多くのクールな機能があり、その上に末尾再帰が最適です :/

于 2013-10-28T00:39:39.837 に答える