JavaScript 末尾再帰

末尾再帰とは、関数内のどこで再帰呼び出しが行われるかを表すものです。再帰コードを読む際にその形式を見分けることは役立ちますが、その形式で関数を書いただけで JavaScript が使うスタック領域が減るとは限りません。このガイドでは、構文とエンジンの動作を区別し、アキュムレーターを使った変換例を示したうえで、トランポリンとループをどのような場合に選ぶとよいかを説明します。

末尾再帰とは

呼び出し元が関数呼び出しの結果をそのまま返し、それ以上の処理を行わない場合、その呼び出しは末尾位置にあります。return total(n - 1, result * n)では、現在の呼び出しは再帰呼び出しの結果を変更せずに返せます。一方、return n * factorial(n - 1)は末尾呼び出しではありません。再帰呼び出しから戻った後、現在の呼び出しで結果にnを掛ける処理が残っているためです。

残っている処理を引数に移すと、末尾呼び出しの形式にできます。引数に後続の計算を持たせることで、基底ケースから累積値をそのまま返せます。これは計算の構造を変えるものであり、エンジンがその処理をどう実行するかを保証するものではありません。

JavaScriptは末尾呼び出しを最適化するのか

末尾呼び出しの形式と末尾呼び出し最適化は別のものです。最適化が行われれば、対象となる呼び出しごとに新しい呼び出しフレームを保持せずに済みます。すべてのエンジンや実行モードでこの最適化が行われるとは限らないため、末尾再帰の構文だけを頼りにしても、スタックの枯渇を確実に防いだり、関数を高速化したりすることはできません。

この形式はアルゴリズムを表現する方法として捉えてください。入力によってはランタイムの呼び出しスタックが対応できる回数を超えて再帰する可能性がある場合、自動的なフレーム再利用に頼らず、明示的なループかトランポリンを使います。性能はエンジンとワークロードによって異なるため、実際に使う環境で測定してください。

再帰関数を末尾呼び出しの形式に変換する

アキュムレーターは、呼び出しをまたいで途中の計算結果を保持します。この例の入力は0以上の整数です。factorial(0)は1となり、負の値や整数でない値は想定する入力範囲に含まれません。

次の例を実行します。コードとのバイト一致を保つため、コード内の出力ラベルは英語のままです。

function factorial(n, result = 1) {
  if (n === 0) return result;
  return factorial(n - 1, result * n);
}

console.log(`Factorial of 5 is ${factorial(5)}`);

デフォルト引数は、factorial(5)のような通常の呼び出しでアキュムレーターを初期化します。再帰の各段階では現在の値をresultに掛けてからnを減らし、基底ケースで累積した積を返します。再帰呼び出しの戻り値に何も適用しないため、この呼び出しは末尾位置にあります。この例は変換方法を示していますが、呼び出しが最適化されない限り、どこまで再帰できるかはランタイムに依存します。

深い再帰にはトランポリンを使う

トランポリンは、繰り返しの呼び出しをループに移します。次の再帰呼び出しをすぐに行う代わりに、各段階で次の処理を表す引数なし関数（サンク）を返します。トランポリンは、ある段階が最終値を返すまで、サンクを一つずつ呼び出します。前の関数が戻った後にループが各サンクを呼び出すため、再帰が進んでも呼び出しフレームが段階ごとに積み重なりません。

このパターンでは、再帰関数がサンクまたは最終値のどちらかを一貫して返し、トランポリンがその規約を判別できる必要があります。次の自己完結した例では、トランポリンが延期された各段階を実行しながら、nから0までの整数を合計します。

このセクションのコードと表示されるラベルや出力は英語のままです。

function trampoline(value) {
  while (typeof value === "function") value = value();
  return value;
}

function sumDown(n, total = 0) {
  if (n === 0) return total;
  return () => sumDown(n - 1, total + n);
}

console.log(trampoline(sumDown(5)));

トランポリンには関数の生成や呼び出しの振り分けに伴うオーバーヘッドがあり、どの再帰アルゴリズムも高速化するわけではありません。再帰的な記述を保つことが重要で、処理が呼び出しスタックの限界を超えるほど深くなる可能性がある場合に役立ちます。単純な繰り返しなら、ループのほうが簡潔なこともよくあります。

arguments.calleeでは末尾再帰にならない理由

n * arguments.callee(n - 1)という式は末尾再帰ではありません。再帰呼び出しから戻った後に、乗算が残っているためです。また、この式が使うarguments.calleeは厳格モードでは利用できず、現代のJavaScriptで適切な書き方でもありません。通常の再帰が適切な場合は、名前付き関数から自分自身を直接呼び出せます。ただし、呼び出しに名前を付けても、その後に処理が残るかどうかは変わりません。

トランポリンとループの選び方

再帰の深さが自然に小さく、再帰的な構造でアルゴリズムが分かりやすくなる場合は、直接再帰を使います。再帰による変換が理解しやすくなるならアキュムレーターを使えますが、末尾呼び出しの形式がスタック深度を保証するわけではない点に注意してください。段階的な再帰構造を保ちながら、反復を使うドライバーで実行する必要がある場合はトランポリンを選びます。その場合は、関数の生成や呼び出しの振り分けが増えることも考慮します。

単純な反復処理には、通常、明示的なループが最も直接的です。反復と状態の更新を見える形にでき、末尾呼び出し最適化にも依存しません。アルゴリズム、想定される深さ、チームにとっての読みやすさ、対象ランタイムで測定した動作を基準に、方法を比較してください。