Recursion is lying to you

あなたの再帰はあなたに嘘をついています 2026年5月9日土曜日 •チュートリアル JavaScript ...あなたに嘘をついています Node Weekly #624 および Javascript Weekly - 2026-06-02 で紹介されました* 再帰は、開発者が早くから学び、長年信頼しているアイデアの1つです。再帰ステップが単純で、ベースケースが正しければ、コードはクリーンで安全だと感じられます。多くの問題は自然に再帰的であり、コードはしばしば私たちが論理を声に出して説明する方法を反映しているため、それはエレガントです。ツリーウォーク、ネストされた構造、および分割統治パターンでは、再帰は明示的なループよりも読みやすい場合があります。 問題は物理的な限界です。正しいベースケースと健全なロジックがあっても、各再帰呼び出しはスタック空間を消費します。ある深さになると、スタックオーバーフローでクラッシュします。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 に組み込まれている解析、ミューテーション、およびタイムゾーンのトラップをカバーしています。 問題設定：再帰は壁にぶつかる 以下のすべてをブラウザコンソールで直接実行できます。 簡単なものから始めましょう：1からnまでのすべての整数の再帰的な合計。 function sum(n) { if (n === 0) return 0; return n + sum(n - 1); } sum(10); // 55 ここで大きな入力をプッシュします： sum(100000); // ほとんどのJSランタイムで RangeError または InternalError: too much recursion 何が起こったのでしょうか？ 関数は論理的には正しいですが、sum の各呼び出しは、その下の呼び出しが返されるまでスタックに残ります。深さ100,000で、ランタイムはスタック空間を使い果たし、例外をスローします。結果が間違っていることとは関係なく、ランタイムが一度に保持できるネストされたフレームの数に対する純粋な物理的な制限です。 テイル再帰の救済物語 通常の次のステップは、テイルコール最適化です。アイデアは単純です：再帰呼び出しを関数の最後の処理にすることで、ランタイムは新しいフレームをプッシュする代わりに同じフレームを再利用できます。 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); // まだ RangeError をスローする可能性があります！ 正しいテイル再帰構造であっても、多くのJavaScriptランタイムは依然として呼び出しごとに新しいスタックフレームを割り当て、大きな深さで例外をスローします。これは、TCO が普遍的な保証であると期待する開発者を驚かせます。 ECMAScript 2015 は、厳密モードで適切なテイルコールを正式に仕様化しましたが、ほとんどのエンジンは一貫してこの機能を採用しませんでした。パフォーマンスの低下により、一部は出荷してその後撤回しました。他のものはまったく実装しませんでした。 結果として、コードが TCO のために正しく構造化されていても、本番JavaScriptでテイル再帰がスタックセーフであると想定することはできません。 フィボナッチに関する注意 フィボナッチは、再帰の教科書の定番例であり、スタック制限にも遭遇しますが、さらに悪いことに、それをさらに悪化させる2番目の問題があります。それは指数時間計算量です。 function fib(n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } 各呼び出しはさらに2つの呼び出しに分岐するため、呼び出しの総数は O(2ⁿ) で増加します。fib(30) はすでに100万回以上の呼び出しを生成します。fib(50) は数百億回です。ブラウザでは、スタック制限に達するずっと前にタブがフリーズするため、障害モードはスタックオーバーフローと同一に見えますが、根本原因はまったく異なります。 フィボナッチのテイル再帰バージョン： 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つの別個の問題です。外部からは同じように見えます（ページがハングするかクラッシュする）が、まったく異なる修正が必要です。 実行時の現実（執筆時点） 執筆時点（2026年5月）では、適切なテイルコール最適化サポートは、JavaScriptランタイム全体で信頼できるものではありません。 実行時エンジン 適切なテイルコール 信頼できますか？ 実用的な注意 Chrome V8 いいえ いいえ スタックセーフなテイル再帰を期待しないでください。 Node.js V8 いいえ いいえ テイル再帰コードでもオーバーフローする可能性があります。 Deno V8 いいえ いいえ Node/Chromeと同じ運用上の期待値です。 Firefox SpiderMonkey いいえ いいえ テイル再帰を安全性の保証として扱わないでください。 Safari JavaScriptCore 一貫しない — JSC はバージョン間で TCO を出荷して撤回しました いいえ それに依存しないでください。リリース間で動作が十分に異なっているため、安定した保証ではありません。 Bun JavaScriptCoreベース エンジン依存、クロスランタイム保証ではありません いいえ 正確なバージョンで検証してください。普遍的な動作を想定しないでください。 重要な点は移植性です。テイル再帰は関数の構造のプロパティであり、スタックの再利用はランタイム実装のプロパティです。1つのエンジンが1つのバージョンでより良く動作したとしても、本番JavaScriptは通常複数のターゲットにまたがり、正しさはオプティマイザー固有の動作に依存すべきではありません。関数は形状としては完全にテイル再帰的であっても、ユーザーが実際に実行する環境では呼び出しごとにスタックを消費する可能性があります。 本番コードのためのより良いパターン すべての再帰関数は反復処理に書き換えることができ、入力の深さが大きくなる可能性がある本番環境では、それが通常最も安全な選択です。反復処理は、ステップごとにスタックフレームを消費しないため、スタックの安全性に関してランタイム最適化に依存しません。 これは再帰的なメンタルモデルを放棄することを意味するものではありません。概念的には再帰的でありながら、明示的なスタックまたはトランポリンを使用して、物理的な制限に達することなく制御フローを管理するコードを書くことができます。 function sumIter(n) { let acc = 0; for (let i = n; i > 0; i--) acc += i; return acc; } sumIter(1000000); // 再帰的なスタックの増加なし トランポリンパターン 読みやすさのために再帰構造を維持したいが、スタックの増加を避けたい場合は、トランポリンを使用できます。これは、最終結果または呼び出す別の関数を返す関数を繰り返し呼び出すループです。 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 に正しさを基づかせないでください。 実用的なチェックリスト 本番クリティカルパスでは、JavaScript で TCO を決して想定しないでください。 現実的な上限でテストしてください。おもちゃの入力サイズではなく。