递归在欺骗你

# 你的递归在欺骗你 来源：https://blog.gaborkoos.com/posts/2026-05-09-Your-Recursion-Is-Lying-to-You/ *收录于 Node Weekly \#624 (https://nodeweekly.com/issues/624) 和 Javascript Weekly - 2026-06-02 (https://javascriptweekly.com/issues/788)* 递归 (https://developer.mozilla.org/en-US/docs/Glossary/Recursion) 是开发者早期学习并长期信赖的概念之一。只要递归步骤简单、基准情况正确，代码就会显得干净且安全。 它之所以优雅是有原因的：许多问题天然适合递归，代码往往能直接反映我们口头解释逻辑的方式。对于树遍历、嵌套结构和分治模式，递归比显式循环更易读。 但问题在于物理限制。即使基准情况正确、逻辑无误，每次递归调用仍然消耗栈空间。当深度达到一定程度，你就会因栈溢出而崩溃。 如果你读过《你的防抖在欺骗你》 (https://blog.gaborkoos.com/posts/2026-03-28-Your-Debounce-Is-Lying-to-You/) 和《你的节流在欺骗你》 (https://blog.gaborkoos.com/posts/2026-03-31-Your-Throttling-Is-Lying-to-You/)，那么本文就是同一模式的递归版本：优雅的抽象，隐藏的操作边缘情况。甚至依赖管理也可能欺骗你，如《你的包管理器在欺骗你》 (https://blog.gaborkoos.com/posts/2026-06-11-Your-Package-Manager-Is-Lying-to-You/) 所述。至于另一类静默失败，《你的 JS Date 在欺骗你》 (https://blog.gaborkoos.com/posts/2026-07-21-Your-JS-Date-Is-Lying-to-You/) 涵盖了 JavaScript Date API 中内置的解析、突变和时区陷阱。 ## 问题设置：递归撞墙 (https://blog.gaborkoos.com/posts/2026-05-09-Your-Recursion-Is-Lying-to-You/#problem-setup%3A-recursion-hits-the-wall) 你可以直接在浏览器控制台中运行以下所有代码。让我们从简单的开始：一个递归求和，计算从 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 时，运行时用尽栈空间并抛出异常。这与结果是否正确无关，纯粹是运行时能同时容纳的嵌套帧数量的物理限制。 ## 尾递归救援的故事 (https://blog.gaborkoos.com/posts/2026-05-09-Your-Recursion-Is-Lying-to-You/#the-tail-recursion-rescue-story) 通常的下一步是尾调用优化 (https://en.wikipedia.org/wiki/Tail_call)。其思路很简单：让递归调用成为函数执行的最后一步，这样运行时可以重用相同的帧，而不是压入新帧。 注意，`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 (https://262.ecma-international.org/6.0/#sec-tail-position-calls) 在严格模式下正式规定了恰当尾调用，但大多数引擎从未一致地采用该特性。有些引擎曾实现过但后来因性能退化而回退。其他引擎则从未实现。结果是，即使代码为 TCO 正确结构化，你也不能假设尾递归在生产环境 JavaScript 中栈安全。 ## 关于斐波那契的说明 (https://blog.gaborkoos.com/posts/2026-05-09-Your-Recursion-Is-Lying-to-You/#a-note-on-fibonacci) 斐波那契 (https://en.wikipedia.org/wiki/Fibonacci_number) 是递归教科书的经典例子，它同样会遇到栈限制，但它还带有第二个问题，使其更糟：**指数时间复杂度**。 `` function fib(n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } `` 每次调用分支成两个更多调用，因此总调用数以 O(2^n) 增长。`fib(30)` 已经做出超过百万次调用；`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); } `` 这个版本以线性时间运行，但在大 `n` 下由于相同的 TCO 不确定性，仍然有栈溢出风险。指数量级的版本对本讨论来说是一个红鲱鱼，因为它因完全不同的原因而失败：栈溢出和指数爆炸是两个独立问题。它们从外部看起来一样（页面挂起或崩溃），但需要完全不同的修复。 ## 运行时现实（撰写本文时） (https://blog.gaborkoos.com/posts/2026-05-09-Your-Recursion-Is-Lying-to-You/#runtime-reality-(at-the-time-of-writing)) 在撰写本文时（2026 年 5 月），跨 JavaScript 运行时的恰当尾调用优化支持并非可靠。 | 运行时 | 引擎 | 你可以依赖的恰当尾调用？ | 实际结论 | |--------|------|---------------------------|----------| | Chrome | V8 | 否 | 不要期望栈安全尾递归。 | | Node.js | V8 | 否 | 尾递归代码仍可能溢出。 | | Deno | V8 | 否 | 与 Node/Chrome 相同的操作预期。 | | Firefox | SpiderMonkey | 否 | 不要将尾递归视为安全保证。 | | Safari | JavaScriptCore | 不一致——JSC 曾跨版本实现并回退过 TCO | 不要依赖它；各版本行为变化较大，不是稳定保证。 | | Bun | JavaScriptCore 为基础 | 引擎相关，非跨运行时保证 | 在确切版本上验证；不要假设通用行为。 | 关键在于可移植性。尾递归是函数结构的属性，而栈重用是运行时的实现属性。即使一个引擎在某个版本中表现更好，生产环境 JavaScript 通常跨越多个目标，正确性不应依赖于优化器特定行为。一个函数在形状上可以完美尾递归，但在用户实际运行的环境中仍可能每调用消耗栈。 ## 生产代码的更好模式 (https://blog.gaborkoos.com/posts/2026-05-09-Your-Recursion-Is-Lying-to-You/#better-patterns-for-production-code) 每个递归函数都可以重写为迭代形式，当输入深度可能增长时，这通常是生产中最安全的选择。迭代不依赖运行时优化来保证栈安全，因为它不会每一步都消耗栈帧。这并不意味着放弃递归的思维模型。你仍然可以编写概念上是递归的代码，但使用显式栈或**蹦床**来控制执行流，而不撞上物理限制。 `` function sumIter(n) { let acc = 0; for (let i = n; i > 0; i--) acc += i; return acc; } sumIter(1000000); // 没有递归栈增长 `` ## 蹦床模式 (https://blog.gaborkoos.com/posts/2026-05-09-Your-Recursion-Is-Lying-to-You/#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)); // 没有栈溢出，精神上仍是尾递归 `` 蹦床用额外的函数分配和调度开销换来了栈安全，因此在保留递归结构比原始性能更重要时最有用。 这种方法以不依赖运行时尾调用行为的方式扩展，这正是当输入深度可能增长时你所需要的。如果递归结构能改善特定问题的可读性，这些技术让你保留这种思维模型，同时做出显式权衡，而非依赖隐式的运行时假设。 一个有用的经验法则是：将递归用于你有控制权的、有界的小深度；**一旦深度由用户驱动、数据驱动或操作上不确定，就切换到迭代控制流**。对于热点路径，对两种风格进行基准测试，但不要基于假定的 TCO 来保证正确性。 ## 实用清单 (https://blog.gaborkoos.com/posts/2026-05-09-Your-Recursion-Is-Lying-to-You/#practical-checklist) - 在生产关键路径上永远不要假设 JavaScript 中的 TCO。 - 使用现实的上限进行测试，而不是玩具输入大小。 - 当深度可能增长时，优先使用迭代实现。 - 将递归视为可读性工具，而非栈安全保证。 ## 结论 (https://blog.gaborkoos.com/posts/2026-05-09-Your-Recursion-Is-Lying-to-You/#conclusion) 递归本身并非敌人，未经验证的运行时假设才是。尾递归的形状并不会自动使 JavaScript 栈安全，而这个差距正是许多“在我机器上能跑”的意外在生产环境中出现的根源。 在递归能提高清晰度且深度确实有界时使用它。当深度可能增长或输入超出你的控制时，优先选择使栈行为显式且可移植的迭代设计。