你的递归正在欺骗你
Recursion is lying to you
递归代码看似优雅简洁，却可能因 JavaScript 运行时缺乏尾调用优化（TCO）而引发栈溢出。文章指出，即便代码结构符合尾递归标准，Chrome、Node.js 等主流环境仍可能分配新栈帧。Fibonacci 等经典案例不仅受限于栈深度，更因指数级时间复杂度导致页面冻结。作者建议在生产环境中，当递归深度不可控时，应优先采用迭代方案或 Trampoline 模式，避免将正确性寄托于不可靠的运行时优化。
递归本身并非敌人，未经验证的运行时假设才是。
- ventana
文章里有个有趣的引用，讨论的是基础的斐波那契递归实现：
> 每次调用会分支出两个新调用，因此总调用次数按 O(2ⁿ) 增长。
嗯，其实不对。如果有人真的去数一下实际发生了多少次递归调用，结果远不是 2 的幂次方：
n | result | # of calls
1 | 1 | 1
2 | 1 | 3
3 | 2 | 5
4 | 3 | 9
5 | 5 | 15
6 | 8 | 25
7 | 13 | 41
8 | 21 | 67
9 | 34 | 109
10 | 55 | 177
11 | 89 | 287
12 | 144 | 465
13 | 233 | 753
14 | 377 | 1219
15 | 610 | 1973
16 | 987 | 3193
17 | 1597 | 5167
18 | 2584 | 8361
19 | 4181 | 13529
20 | 6765 | 21891
好奇的人接着会算出实际比率：
n | result | # of calls | ratio
1 | 1 | 1 | 1
2 | 1 | 3 | 3
3 | 2 | 5 | 1.6666666666666667
4 | 3 | 9 | 1.8
5 | 5 | 15 | 1.6666666666666667
6 | 8 | 25 | 1.6666666666666667
7 | 13 | 41 | 1.64
8 | 21 | 67 | 1.6341463414634145
9 | 34 | 109 | 1.626865671641791
10 | 55 | 177 | 1.6238532110091743
11 | 89 | 287 | 1.621468926553672 […]
- RajT88
这不是 CS 101 吗？递归写起来更简单，但性能更差，风险也更大，不如迭代。
- eventualcomp
怎么没提动态规划来处理递归函数？动态规划就是为这个设计的，你甚至不需要像那个 trampoline 那样频繁折腾堆内存。实例化你的数组，确保设置好你的基本情况和循环，以免掉进 `undefined` 的坑里，然后反向递归即可。
- 10000truths
处理调用栈递归的麻烦，归根结底是因为缺乏强大的静态分析工具来检测栈使用情况。在现有的少数能生成应用程序构建时调用图的工具中，几乎没有任何一个能输出机器可读的格式。据我所知，目前最先进的方案是 LLVM 的 dot-callgraph pass，但即便如此，它输出的也是 DOT 格式，而不是像 CSV 或 JSON 这样更广泛采用的格式。除此之外，你就得自己造轮子了，要么通过运行时分析，要么写个自定义编译器插件。
- okzgn
参考链接：https://v8.dev/blog/modern-javascript#proper-tail-calls (Recursion, Proper tail calls, 2016)
Proper Tail Calls 曾经在实验性标志后实现过，但从未默认发布——这些标志后来也被移除了。