概要
再帰とは「自分を呼び出す関数」ではない。
それは**“分割と再構築を制御し、状態と深さを扱いながら計算の本質を定義する構造”**である。
JavaScriptは再帰に対して強力だが、スタックサイズの制限 / パフォーマンスの劣化 / ブラウザ依存の動作不安定など、
再帰設計を誤ると 実用レベルでは破綻 する。
本稿では、末尾再帰・トランポリン・再帰→反復の変換など、
JavaScriptで再帰処理を安全かつ効率的に扱うための設計手法を解説する。
1. 再帰とは「自己参照による分割と帰納」
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
- ✅ 再帰とは「状態の縮小と組み合わせによる答えの構築」
- ❌ スタックサイズにより
RangeError: Maximum call stack size exceededを起こす可能性
2. 末尾再帰（Tail Call Optimization）の理論と罠
function factorial(n, acc = 1) {
if (n <= 1) return acc;
return factorial(n - 1, acc * n);
}
- ✅ 最後の処理が再帰呼び出し → TCO対象
- ❌ JavaScriptはTCOが仕様上定義されているが、現在は未サポート
- 2025現在：Safari以外では末尾再帰は最適化されない
3. トランポリン構造：再帰の分解による実行
function trampoline(fn) {
while (typeof fn === 'function') {
fn = fn();
}
return fn;
}
function sum(n, acc = 0) {
if (n === 0) return acc;
return () => sum(n - 1, acc + n); // 関数を返す
}
trampoline(() => sum(100000));
- ✅ 関数を返し続けて1ステップずつ実行 → スタック破綻しない
- ✅ 深さのある処理でも安全に扱える再帰エミュレーション
4. 再帰 → 反復への変換
function factorialIterative(n) {
let result = 1;
for (let i = 2; i <= n; i++) {
result *= i;
}
return result;
}
- ✅ 再帰は設計が直感的
- ✅ 反復は実行が効率的（GC、最適化）
5. 再帰パターンの分類と選定
- 単純再帰（n → n-1） → TCO / トランポリンで安全に
- 木構造 / グラフ探索（DFS） → スタック管理 or Stack併用
- 巡回再帰（状態記憶） → メモ化再帰 or DPに展開
設計判断フロー
① この再帰は「深さが大きくなる可能性」があるか？ → トランポリン or 反復へ変換
② 状態保持（キャッシュ、accumulator）が必要か？ → 末尾再帰設計 or メモ化再帰
③ パフォーマンス上限（ms / call depth）に触れていないか？ → GC/最適化観点から再設計
④ コードの直感性を優先するか？ → 読みやすさと安全性のバランス設計
よくあるミスと対策
❌ 10万回再帰でブラウザがクラッシュ
→ ✅ トランポリン化 + 関数返却構造で安全化
❌ TCOを期待して末尾再帰を書いたが何も変わらなかった
→ ✅ JavaScriptではTCOは非実装 → 明示的に再設計が必要
❌ 複雑なロジックを再帰で書いてスタックと戦っている
→ ✅ スタックは有限 → 明示的に自分で制御する設計へ変換
結語
再帰とは「自分を呼び出す関数」ではない。
それは**“状態を縮小し、構造を保ちながら、帰納的に意味を定義する制御の方法”**である。
- JavaScriptでは TCOは理論上のみ存在し、実用性は限られる
- トランポリン構造は再帰安全性の強力な手法
- 再帰 → 反復の変換はパフォーマンス上の王道
- 設計時に 深さ・安全性・速度・見通しをすべて考慮する
JavaScriptにおける再帰処理設計とは、
“スタックという制限下で意味と構造を共存させるための表現と制御の設計戦略”である。