末尾再帰最適化とは？
末尾再帰最適化（Tail Call Optimization：TCO）とは、末尾再帰になっている関数を、実行時に繰り返し処理のように最適化する仕組みです。これにより、再帰呼び出しを繰り返してもスタックフレームが増えず、メモリ使用量を抑えることができます。
ただし、現在のJavaScriptではほとんどのブラウザやNode.jsで末尾再帰最適化は実装されていません。そのため、実際の開発では末尾再帰よりもループ処理を使用することが一般的です。
末尾再帰とは？
末尾再帰とは、関数の最後に行う処理が再帰呼び出しだけになっている再帰関数です。再帰呼び出しの戻り値に対して追加の計算を行わないことが条件になります。
例えば、次のようなコードは末尾再帰です。
function countdown(n) {
if (n === 0) {
return;
}
console.log(n);
return countdown(n - 1);
}
最後の処理がcountdown()の呼び出しだけになっています。
通常の再帰との違い
通常の再帰では、再帰呼び出しが終了したあとに計算を続ける必要があるため、途中の状態をスタックへ保存し続けます。
一方、末尾再帰では、再帰呼び出しのあとに処理がないため、理論上は現在のスタックフレームを再利用できます。
| 比較項目 | 通常の再帰 | 末尾再帰 |
|---|---|---|
| 再帰呼び出し後の処理 | ある | ない |
| スタックフレーム | 積み重なる | 再利用できる（最適化される場合） |
| メモリ使用量 | 再帰回数に比例して増える | 最適化されれば一定になる |
通常の再帰の例
次の階乗を求める関数は、再帰呼び出しのあとに掛け算を行うため、末尾再帰ではありません。
function factorial(n) {
if (n === 0) {
return 1;
}
return n * factorial(n - 1);
}
console.log(factorial(5));
factorial(n - 1)が終了したあとにn *の計算が残っているため、途中の状態を保持する必要があります。
末尾再帰の例
次のように途中結果を引数で受け渡すと、末尾再帰にできます。
function factorial(n, result = 1) {
if (n === 0) {
return result;
}
return factorial(n - 1, result * n);
}
console.log(factorial(5));
この関数では、最後に実行される処理が再帰呼び出しだけになっています。
JavaScriptでは注意が必要
ECMAScript 2015（ES6）では末尾再帰最適化が仕様として定義されました。しかし、多くのJavaScriptエンジンでは実装されていません。
そのため、末尾再帰で記述してもスタックフレームは削減されず、大量の再帰ではMaximum call stack size exceededが発生する可能性があります。
ループ処理との比較
| 方法 | 現在のJavaScriptでの実用性 |
|---|---|
| 通常の再帰 | 深い再帰ではスタックオーバーフローの可能性がある。 |
| 末尾再帰 | 理論上は効率的だが、多くの実行環境では最適化されない。 |
| for・whileループ | 最も安全で高速な方法として推奨される。 |
まとめ
- 末尾再帰は、最後の処理が再帰呼び出しだけになっている再帰関数である。
- 末尾再帰最適化により、理論上はスタックフレームを再利用できる。
- 通常の再帰では途中の計算が残るため、スタックが積み重なる。
- 現在のJavaScriptでは、多くのブラウザやNode.jsで末尾再帰最適化は実装されていない。
- 実際の開発では、深い繰り返し処理には
forやwhileを使用することが一般的である。