HN 日本語サマリー

← 一覧へ戻る
プログラミング

Recursion is lying to you

Recursion is lying to you (blog.gaborkoos.com)

23 pointsby theanonymousone22 コメント

要約

この記事は、JavaScriptにおける再帰処理の落とし穴について解説しています。再帰関数はエレガントですが、各呼び出しがスタックメモリを消費するため、深い再帰はスタックオーバーフローを引き起こす可能性があります。Tail Call Optimization (TCO) が期待されるものの、JavaScriptランタイムでのサポートは一貫しておらず、実用的ではない場合が多いと指摘しています。そのため、本番環境では反復処理やトランポリンパターンなどの代替手段が推奨されています。

全文翻訳

Your Recursion Is Lying to You

Featured in Node Weekly #624 and Javascript Weekly - 2026-06-02

再帰は、開発者が早い段階で学び、長年信頼してきた概念の一つです。再帰ステップが単純で、ベースケースが正しければ、コードはクリーンで安全だと感じられます。

その理由は、多くの問題が本質的に再帰的であり、コードがしばしば論理を声に出して説明する方法を反映しているからです。ツリーウォーク、ネストされた構造、分割統治パターンなどでは、明示的なループよりも再帰の方が読みやすい場合があります。

しかし、そこには物理的な限界があります。正しいベースケースと健全なロジックがあっても、各再帰呼び出しはスタック領域を消費します。ある深さに達すると、スタックオーバーフローでクラッシュします。

Your Debounce Is Lying to You や Your Throttling Is Lying to You を読んだことがあるなら、これは同じパターンの再帰バージョンです。エレガントな抽象化、隠された運用上のエッジです。依存関係管理でさえあなたを騙す可能性があることは、Your Package Manager Is Lying to You で探求されています。別の種類のサイレントフェイルについては、Your JS Date Is Lying to You が JavaScript Date API に組み込まれたパース、ミューテーション、タイムゾーンの落とし穴をカバーしています。

Problem Setup: Recursion Hits The Wall

以下のすべてをブラウザのコンソールで直接実行できます。まずは簡単なものから始めましょう。1からnまでのすべての整数の再帰的な合計です。

function sum(n) {
  if (n === 0) return 0;
  return n + sum(n - 1);
}

sum(10); // 55

ここで大きな入力を試してみましょう。

sum(100000); // RangeError or InternalError: most JS runtimes in too much recursion

何が起こったのでしょうか? 関数は論理的には正しいですが、sum の各呼び出しは、その下の呼び出しが返るまでスタック上に残ります。深さ100,000で、ランタイムはスタック領域を使い果たし、例外をスローします。これは結果が間違っていることとは無関係で、純粋にランタイムが一度に保持できるネストされたフレームの数に対する物理的な制限です。

The Tail Recursion Rescue Story

通常次のステップは、末尾呼び出し最適化(TCO)です。その考え方はシンプルです。再帰呼び出しを関数の最後の操作にすることで、ランタイムは新しいフレームをプッシュする代わりに同じフレームを再利用できます。

sum 関数は、再帰呼び出しが最後の行に現れるにもかかわらず、末尾再帰ではありません。sum(n - 1) が返った後も、まだ保留中の作業があります。その結果は n に加算される必要があります。呼び出しが末尾位置にあるのは、その戻り値が、後続の計算なしに即座に転送される場合のみです。

末尾再帰バージョンは、その保留中の状態をアクセラレータ(アキュムレータ)に移動させます。

function sumTR(n, acc = 0) {
  if (n === 0) return acc;
  return sumTR(n - 1, acc + n);
}

sumTR(10); // 55

ここでは sumTR(...) が最後の操作であり、保留中の + やその他の計算はありません。実行中の合計はスタックフレームの待機ではなく、acc に保持されます。理論的には、TCOを実装したランタイムは、深さに関係なく定数スタック空間でこれを実行できます。

ここで同じ負荷テスト入力を繰り返してみましょう。

sumTR(100000); // may still throw RangeError!

正しい末尾再帰構造であっても、多くのJavaScriptランタイムは依然として呼び出しごとに新しいスタックフレームを割り当て、大きな深さで例外をスローします。これは、TCOが普遍的な保証であると期待している開発者を驚かせます。ECMAScript 2015 は、strict モードで適切な末尾呼び出しを正式に仕様化しましたが、ほとんどのエンジンは一貫してこの機能を採用しませんでした。パフォーマンスの低下により、一部のエンジンはそれを実装してから元に戻しました。他のエンジンは全く実装しませんでした。その結果、コードがTCOのために正しく構造化されていても、本番のJavaScriptで末尾再帰がスタックセーフであると仮定することはできません。

A Note on Fibonacci

フィボナッチ数は、再帰の教科書的な例としてよく使われますが、スタック制限に達するだけでなく、さらに悪いことに、指数関数的な時間計算量という第二の問題を抱えています。

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

各呼び出しはさらに2つの呼び出しに分岐するため、呼び出しの総数は O(2ⁿ) で増加します。(より正確には、Θ(φⁿ) で φ ≈ 1.6 ですが、どちらも指数関数的な成長を表すため、O(2ⁿ) と近似されることが多いです。)fib(30) はすでに100万回以上の呼び出しを生成します。fib(50) は数兆回に及びます。ブラウザでは、スタック制限に達するずっと前にタブがフリーズするため、失敗モードはスタックオーバーフローと同一に見えますが、根本原因は全く異なります。

(その φ の導出、漸化式から特性方程式への変換、そしてこの記事へのコメントがどのように最初の単純化を捉えたかの話は、import chaos newsletter のコンパニオンである Director's Cut にあります。)

フィボナッチの末尾再帰バージョンは次のようになります。

function fibTR(n, a = 0, b = 1) {
  if (n === 0) return a;
  if (n === 1) return b;
  return fibTR(n - 1, b, a + b);
}

このバージョンは線形時間で実行されますが、TCOの不確実性により、大きな n では依然としてスタックオーバーフローのリスクがあります。指数バージョンは、全く異なる理由で失敗するため、この議論では的外れです。スタックオーバーフローと指数的な増加は、2つの別々の問題です。外部からは同じように見えます(ページがハングしたりクラッシュしたりする)が、全く異なる修正が必要です。

Runtime Reality (At The Time Of Writing)

執筆時点(2026年5月)では、適切な末尾呼び出し最適化のサポートは、JavaScriptランタイム全体で期待できるものではありません。

RuntimeEngineProper Tail Calls You Can Rely On?Practical Take
ChromeV8NoDo not expect stack-safe tail recursion.
Node.jsV8NoTail-recursive code can still overflow.
DenoV8NoSame operational expectation as Node/Chrome.
FirefoxSpiderMonkeyNoDo not treat tail recursion as a safety guarantee.
SafariJavaScriptCoreInconsistent — JSC has shipped and walked back TCO across versionsDo not rely on it; behavior has varied enough across releases that it is not a stable guarantee.
BunJavaScriptCore-basedEngine-dependent, not a cross-runtime guaranteeVerify on exact version; do not assume universal behavior.

重要な点は移植性です。末尾再帰は関数の構造の特性であり、スタックの再利用はランタイム実装の特性です。たとえあるエンジンが特定のバージョンでより良く動作したとしても、本番のJavaScriptは通常複数のターゲットにまたがっており、正しさはオプティマイザー固有の動作に依存すべきではありません。関数は末尾再帰の形状としては完璧であっても、ユーザーが実際に実行する環境では呼び出しごとにスタックを消費する可能性があります。

Better Patterns for Production Code

すべての再帰関数は反復処理で書き直すことができ、入力の深さが大きくなる可能性がある本番環境では、それが最も安全な選択肢となることが多いです。反復処理はスタックフレームをステップごとに消費しないため、スタックセーフティのためにランタイムの最適化に依存しません。これは再帰的なメンタルモデルを捨てることを意味しません。概念的には再帰的でありながら、明示的なスタックやトランポリンを使用して物理的な制限に達することなく制御フローを管理するコードを書くことができます。

function sumIter(n) {
  let acc = 0;
  for (let i = n; i > 0; i--) acc += i;
  return acc;
}

sumIter(1000000); // no recursive stack growth

The Trampoline Pattern

可読性のために再帰構造を維持したいが、スタックの増加を避けたい場合は、トランポリンを使用できます。これは、最終結果または次に呼び出す関数を返す関数を繰り返し呼び出すループです。

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)); // no stack overflow, still tail-recursive in spirit

トランポリンは、スタックセーフティと引き換えに、追加の関数割り当てとディスパッチオーバーヘッドが発生するため、再帰構造の維持が生のパフォーマンスよりも重要な場合に最も役立ちます。

このアプローチは、ランタイムの末尾呼び出しの動作に依存しない方法でスケーリングします。これは、入力の深さが大きくなる可能性がある場合にまさに望むものです。再帰構造が特定の問題の可読性を向上させる場合、これらのテクニックを使用すると、暗黙的なランタイムの仮定ではなく、明示的なトレードオフでそのメンタルモデルを維持できます。

経験則として、再帰は小さく、深さが制限されている場合にのみ使用し、深さがユーザー駆動型、データ駆動型、または運用上不確かな場合は、すぐに反復制御フローに切り替えてください。ホットパスの場合は、両方のスタイルをベンチマークしますが、正しさを仮定されたTCOに基づかないでください。

Practical Checklist

  • 本番クリティカルなパスでは、JavaScriptでTCOを絶対に仮定しないでください。
  • 現実的な上限値でテストし、おもちゃの入力サイズでテストしないでください。
  • 深さが大きくなる可能性がある場合は、反復実装を優先してください。
  • 再帰を可読性のためのツールとして扱い、スタックセーフティの保証としては扱わないでください。

Conclusion

再帰自体が悪なのではなく、検証されていないランタイムの仮定が悪なのです。末尾再帰の形状が自動的にJavaScriptをスタックセーフにするわけではなく、そのギャップが本番環境で多くの「私のマシンでは動く」という驚きの原因となります。

再帰は、明瞭さが向上し、深さが実際に制限されている場所で使用してください。深さが大きくなる可能性がある場合や、入力が制御外である場合は、スタックの動作を明示的かつポータブルにする反復設計を優先してください。

馴染みのある抽象化とその運用上の限界との間の同じギャップは、データがコールスタックから完全に離れる場合にも現れます。Your JSON Is Lying to You は、JavaScriptデータがシステム境界を越えるときにシリアライゼーションが値をどのように変更し、型を失うかを説明しています。Your Modules Are Lying to You は、モジュール解決、評価、キャッシュ、およびCommonJS/ESMの相互運用を通じて同じパターンを追跡しています。