JavaScript のスタック限界と再帰：壁にぶつかる前に知るべきこと

当記事は Node Weekly #624 および JavaScript Weekly - 2026 年 6 月 2 日 に掲載されました。

再帰の美しさと物理的な限界

再帰（recursion）は開発者が信頼して以来の概念ですが、その裏には物理的な制約が存在します。

• ** Elegance（洗練さ）**
  • ツリー遍歴やネスト構造において、明示的なループよりも記述が簡単で読みやすいです。
  • ベースケースと論理が正しければ、コードは安全に見えます。
• 致命的なリスク
  • 各再帰呼び出しはスタック空間を消費します。
  • スタックの深さに到達すると、「Your Debounce Is Lying to You」のようにスタックオーバーフローが発生しクラッシュします。
  • これは結果の誤りではなく、ランタイムが一時的に保持できるフレーム数の限界です。

---

問題の設定：スタックオーバーフローの仕組み

シンプルな再帰関数からスタックが枯渇する様子を見てみましょう。

function sum(n) {
  if (n === 0) return 0;
  // 論理は正しいが、スタックを深く掘る
  return n + sum(n - 1); 
}

sum(10);      // ✅ 55
sum(100000);  // ❌ RangeError: "too much recursion" (多くのランタイム)

何が起きたのか？

• sum

  の各呼び出しは、下の関数が返ってくるまでスタックに残ります。
• 深さ 100,000 に達すると、ランタイムのスタック容量を超えて例外が投げられます。

---

テール再帰（TCO）による解決策とその落とし穴

「再帰呼び出しを最後に行い、同じフレームを再利用する」という**テール呼び出し最適化（TCO: Tail Call Optimization）**が一般的ないくつかの解決策として挙げられます。

TCO とは

• 再帰呼び出しを関数の最後に配置することで、新しいスタックフレームを追加せず、既存のフレームを再利用します。
• 注意：

  sum(n)

  はテール再帰ではありません。結果に

  n

  を加算する処理が残り、未処理の計算があるためです。

TCO 実装例（累加器付き）

未処理の状態を積算器 (

acc

) に移し、最後の行として再帰呼び出しを行います。

function sumTR(n, acc = 0) {
  if (n === 0) return acc; // ✅ テール位置
  return sumTR(n - 1, acc + n); // ✅ テール位置
}

// 理論的にはスタックを消費しないはずですが...
sumTR(100000); 

⚠️ TCO の現実は厳しいです： 多くの JavaScript ランタイムは、構造上テール再帰であっても新しいスタックフレームを割り当て続けます。

• ECMAScript 2015 で厳密モードでの仕様化されていますが、ほとんどのエンジンが一貫して実装していないのが現状です。
• エンジンの一部は性能劣化のリスクから機能を実装しなくなりました。

重要な結論：コードが TCO に最適化されていても、本番環境で再帰がスタック安全であると仮定することはできません。

---

別の課題：フィボナッチ数列と時間計算量

フィボナッチ数列は再帰の教科書的例題ですが、スタック限界とは別に**指数関数的な時間計算量 $O(2^n)$**という深刻な問題を抱えています。

通常の再帰（爆発的に遅い）

function fib(n) {
  if (n <= 1) return n;
  // O(2^n) の呼び出し数増加
  return fib(n - 1) + fib(n - 2); 
}

• fib(30)

  で 100 万回、

  fib(50)

  で数十十億回の呼び出しが発生します。
• ブラウザではスタック限界に達する前にタブがフリーズします。

TCO 版フィボナッチ

function fibTR(n, a = 0, b = 1) {
  if (n === 0) return a;
  if (n === 1) return b;
  return fibTR(n - 1, b, a + b); // O(n) で改善されたが、TCO の不確実性は残る
}

• 時間計算量は線形化されましたが、依然としてスタックオーバーフローのリスク（ランタイム依存）が残ります。

---

ランタイム別の TCO サポート状況（2026 年 5 月時点）

正しいテール呼び出し最適化は、すべての環境で期待することはできません。移植性を確保する上で重要な情報は以下の通りです。

ランタイム	エンジン	TCO の信頼性	実用的な結論
Chrome	V8	❌ なし	スタック安全なテール再帰は期待しないこと。
Node.js	V8	❌ なし	テール再帰でもスタックオーバーフローする可能性があります。
Deno	V8	❌ なし	Chrome/Node と同じ運用前提です。
Firefox	SpiderMonkey	❌ なし	TCO を安全性の保証として扱わないこと。
Safari	JavaScriptCore	⚠️ 不規則	バージョン間で実装の有無が変わります（安定しない）。
Bun	JSCore ベース	⚠️ エンジン依存	クロスランタイムの保証はなく、バージョン確認が必要です。

重要: テール再帰はコード構造上の性質ですが、スタック再利用はランタイムの実装特性です。複数ターゲットを扱う本番環境では、最適化に依存せず設計すべきです。

---

本番コード向けのパターン

スタック限界を超えるリスクを避けるためには、以下のアプローチが推奨されます。

1. 反復的実装（最安全）

すべての再帰関数をループに変換できます。ステップごとにスタックフレームを消費しないため、最も安全です。

function sumIter(n) {
  let acc = 0;
  for (let i = n; i > 0; i--) acc += i; // ✅ スタック成長なし
  return acc;
}
sumIter(1000000); // 動作正常

2. トランポリンパターン（再帰性を維持したい場合）

可読性を保ちつつスタックの増加を避けたい場合に有効です。関数を返すループで制御します。

// トランポリンの仕組み
function trampoline(fn) {
  let result = fn;
  while (typeof result === 'function') {
    result = result(); // ✅ スタックを消費せず、イテレーティブに実行
  }
  return result;
}

// 再帰的な精神を保ったまま、スタック安全に呼び出す
function sumTrampoline(n, acc = 0) {
  if (n === 0) return acc;
  // 関数（次のステップ）を返すことで、ループ側が制御する
  return () => sumTrampoline(n - 1, acc + n); 
}

trampoline(() => sumTrampoline(100000)); // ✅ スタックオーバーフローなし

---

実践チェックリスト

以下の項目を確認しながらコーディングを進めてください。

• TCO に依存しない：本番クリティカルなパスで TCO を常に有効であると仮定しないこと。
• テストケースを厳格化：トイサイズの入力だけでなく、現実的な上限値（10 万〜）でも動作確認すること。
• 優先順位の決定：深さが成長する可能性がある場合は、反復的実装を優先すること。
• 目的の明確化：再帰は「読みやすさのためのツール」であり、「スタック安全性の保証」ではないと認識すること。

---

結論

再帰自体が悪いわけではありませんが、検証されていないランタイムの仮定に依存するのは危険です。

• ✅ 推奨: 可読性向上や深度が明確に有界な場合に再帰を使用。
• ⚠️ 注意: 深度がユーザー入力などに依存しコントロール外にある場合は、明示的かつ移植性の高い反復的な設計を心がけること。

「私のマシンでは動く」で妥協せず、本番環境の多様なランタイム動作を考慮した保守的なコード構築を目指しましょう。