再帰関数には、次の 2 つの要素が必要です。
- 再帰呼び出し
- 戻り値のカウントを保持する場所。
「通常の」再帰関数は (2) をスタック フレームに保持します。
通常の再帰関数の戻り値は、次の 2 種類の値で構成されます。
あなたの例を見てみましょう:
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 ループのように動作します。
それを最適化するかどうかはコンパイラ次第です。