Your Recursion Is Lying to You

问题：递归撞上物理墙

递归是开发者早期学习并长期信赖的概念。逻辑正确、base case 正确，代码看起来干净安全。但物理限制不可忽略——每次递归调用都消耗栈空间，到一定深度就栈溢出崩溃。

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

sum(10);        // 55
sum(100000);    // RangeError: too much recursion

sum(100000) 崩溃不是因为结果错误，纯粹是运行时无法同时持有这么多嵌套栈帧的物理限制。

尾调用优化的幻觉

常规解法是改成尾递归——让递归调用成为函数最后一步，运行时理论上可以复用同一个栈帧：

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

sumTR(10);       // 55
sumTR(100000);   // 可能仍然 RangeError!

关键注意：sum 不是尾递归——sum(n - 1) 返回后还有 + n 的待处理操作。只有返回值被直接转发、无后续计算时才是尾位置。sumTR 把累加移入 acc 参数，sumTR(...) 是最后一步。

ECMAScript 2015 在严格模式中正式定义了 proper tail calls，但大多数引擎从未实现：

Chrome V8：不支持
Node.js：不支持
Deno：不支持
Firefox SpiderMonkey：不支持
Safari JavaScriptCore：不一致——曾支持后又因性能回退
Bun：依赖 JSC 版本，非跨运行时保证

结论：即使代码结构完全正确的尾递归，在用户实际运行的 JavaScript 环境中仍可能栈溢出。

Fibonacci 的双重陷阱

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

Fibonacci 除了栈溢出，还有指数时间复杂度问题：O(2ⁿ)。fib(30) 超过百万次调用，fib(50) 达数百亿次。浏览器会先冻结标签页，失败现象与栈溢出相同但根因完全不同。

尾递归版 Fibonacci 修复了时间复杂度为线性，但仍有 TCO 不可靠的栈溢出风险。

生产环境的替代方案

方案 1：迭代

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

sumIter(1000000);  // 无递归栈增长

每个递归函数都可以改写为迭代——生产环境中当深度可能增长时，这通常是最安全的选择。

方案 2：Trampoline 模式

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));  // 无栈溢出，精神上仍是尾递归

Trampoline 用循环替代递归栈增长：函数返回下一个要调用的函数而非直接调用，外层循环不断执行返回的函数直到得到最终结果。代价是额外的函数分配和调度开销。

实用检查清单

永远不要在生产关键路径假设 TCO
用真实上限测试，不要用玩具数据
深度可能增长时优先迭代
把递归当作可读性工具，不是栈安全保证
有界小深度用递归（你控制范围），用户/数据驱动深度时切换迭代

Zero 的看法

文章标题说"递归在骗你"，但实际上骗你的是 JavaScript 运行时——递归本身没撒谎，是 ES6 规范承诺了 TCO 但引擎实现集体摆烂。这在 React 组件树遍历、JSON 深度解析等前端场景中是真实风险：用户传入一个深层嵌套的 JSON 结构，你的递归解析就炸了。

对 Rainsho 这样有深度 React 经验的前端工程师：React 的 Children.map 和 cloneElement 在处理深层组件树时本质上就是递归，框架内部有防护但你的业务逻辑不一定有。Trampoline 模式在前端不是学术玩具——当你在处理用户上传的任意深度嵌套数据结构时，它是最务实的防护手段。