125

末尾再帰の仕組みと、通常の再帰との違いがほぼ理解できました。戻りアドレスを記憶するためにスタックを必要としない理由がわかりません。

// tail recursion
int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

int factorial (int n) {
    return fac_times (n, 1);
}

// normal recursion
int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

末尾再帰関数で関数自体を呼び出した後は何もすることはありませんが、私には意味がありません。

4

8 に答える 8

174

コンパイラはこれを単純に変換できます

int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

このようなものに:

int fac_times (int n, int acc) {
label:
    if (n == 0) return acc;
    acc *= n--;
    goto label;
}
于 2013-03-20T09:11:50.690 に答える
60

「リターンアドレスを記憶するためにスタックを必要としない」理由を尋ねます。

これをひっくり返したいと思います。戻りアドレスを記憶するためにスタックを使用しますトリックは、末尾再帰が発生する関数がスタック上に独自のリターン アドレスを持ち、呼び出された関数にジャンプするときに、これを独自のリターン アドレスとして扱うことです。

具体的には、末尾呼び出しの最適化なし:

f: ...
   CALL g
   RET
g:
   ...
   RET

この場合、gが呼び出されると、スタックは次のようになります。

   SP ->  Return address of "g"
          Return address of "f"

一方、末尾呼び出しの最適化では、次のようになります。

f: ...
   JUMP g
g:
   ...
   RET

この場合、gが呼び出されると、スタックは次のようになります。

   SP ->  Return address of "f"

明らかに、g戻るときは、呼び出し元の場所に戻りますf

EDIT : 上記の例では、ある関数が別の関数を呼び出すケースを使用しています。関数がそれ自体を呼び出すときのメカニズムは同じです。

于 2013-03-20T09:12:43.980 に答える
13

特にアキュムレータが使用されている場合、末尾再帰は通常、コンパイラによってループに変換されます。

// tail recursion
int fac_times (int n, int acc = 1) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

次のようなものにコンパイルされます

// accumulator
int fac_times (int n) {
    int acc = 1;
    while (n > 0) {
        acc *= n;
        n -= 1;
    }
    return acc;
}
于 2013-03-20T09:12:30.350 に答える
12

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

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

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

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

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

あなたの例を見てみましょう:

int factorial (int n) {
    if (n == 0) return 1;
    else 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 を見てみましょう:

int factorial (int n) {
    int helper(int num, int accumulated)
        {
            if num == 0 return accumulated
            else return helper(num - 1, accumulated*num)
        }
    return helper(n, 1)    
}

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

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

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

再帰テンプレート

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

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

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

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

見て:

type tail(n):
    type 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)

違いを見ます?

テールコールの最適化

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

それを最適化するかどうかはコンパイラ次第です。

于 2013-10-28T00:44:53.173 に答える
8

以下は、再帰関数がどのように機能するかを示す簡単な例です。

long f (long n)
{

    if (n == 0) // have we reached the bottom of the ocean ?
        return 0;

    // code executed in the descendence

    return f(n-1) + 1; // recurrence

    // code executed in the ascendence

}

末尾再帰は単純な再帰関数であり、関数の最後で再帰が行われるため、昇順でコードが実行されることはありません。テイル再帰モジュロとして知られるより複雑な最適化

于 2013-03-20T15:17:00.290 に答える
0

再帰は内部実装に関連するものであるため、私の答えはもっと推測です。

末尾再帰では、再帰関数は同じ関数の最後で呼び出されます。おそらくコンパイラは以下の方法で最適化できます:

  1. 進行中の関数を終了させます(つまり、使用済みのスタックがリコールされます)
  2. 関数の引数として使用される変数を一時ストレージに格納します
  3. この後、一時的に保存された引数を使用して関数を再度呼び出します

ご覧のとおり、同じ関数の次の反復の前に元の関数を終了しているため、実際にはスタックを「使用」していません。

ただし、関数内に呼び出されるデストラクタがある場合、この最適化は適用されない可能性があります。

于 2013-03-20T09:05:17.293 に答える