递归：函数式中的“循环替代品”
——为什么尾递归在 JS 中受限？如何用 trampoline 避免栈溢出？
“循环是命令式的‘goto’，
递归是函数式的‘数学定义’。”
一、为什么函数式编程偏爱递归？
在函数式语言中：
- 没有
for、while（避免可变状态） - 只有表达式和函数调用
所以，递归是唯一能实现重复逻辑的方式。
示例：计算阶乘
命令式（循环 + 变量）
js
function factorial(n) {
let result = 1;
for (let i = 2; i <= n; i++) {
result *= i; // 突变！
}
return result;
}依赖变量 i 和 result 的突变。
函数式（递归）
js
const factorial = n =>
n <= 1 ? 1 : n * factorial(n - 1);没有变量，没有突变，只有数学定义的直接翻译。
二、递归的问题：栈溢出（Stack Overflow）
问题根源：调用栈无限增长
js
factorial(5)
// 展开为：
5 * factorial(4)
5 * (4 * factorial(3))
5 * (4 * (3 * factorial(2)))
5 * (4 * (3 * (2 * factorial(1))))
5 * (4 * (3 * (2 * 1))) // 开始回弹每层递归都占用栈帧，直到最深层才开始计算。
当 n=10000，调用栈深度为 10000 → 栈溢出。
三、优化方案 1：尾递归（Tail Recursion）
什么是尾递归？
递归调用是函数的最后一个操作，无需保留当前栈帧。
js
const factorial = (n, acc = 1) =>
n <= 1 ? acc : factorial(n - 1, acc * n);执行过程：
factorial(5, 1)
factorial(4, 5)
factorial(3, 20)
factorial(2, 60)
factorial(1, 120) → 120理想情况下，编译器可以将其优化为循环，O(1) 栈空间。
为什么 JS 中尾递归受限？
尽管 ES6 规范要求支持尾调用优化（TCO），但：
| 引擎 | TCO 支持情况 |
|---|---|
| V8 (Chrome) | 已放弃实现（性能权衡） |
| SpiderMonkey (Firefox) | 仅在严格模式下部分支持 |
| JavaScriptCore (Safari) | 曾支持，但后续版本不稳定 |
现实：JS 引擎普遍不支持 TCO，因为：
- 调试困难（栈被重写）
- 性能收益有限
try/catch等机制干扰优化
所以，即使你写了尾递归，依然可能栈溢出。
四、解决方案：Trampoline（蹦床函数）
核心思想：
不让函数直接递归调用自己，而是返回一个“继续执行”的函数（thunk）。
由一个外部循环（trampoline）来逐个执行这些 thunk。
实现 trampoline
js
function trampoline(fn) {
return function(...args) {
let result = fn(...args);
while (typeof result === 'function') {
result = result(); // 执行 thunk，直到返回最终值
}
return result;
};
}改造尾递归为蹦床
js
function factorial(n, acc = 1) {
if (n <= 1) return acc;
return () => factorial(n - 1, acc * n); // 返回 thunk
}
const safeFactorial = trampoline(factorial);
safeFactorial(10000); // 不会栈溢出执行流程：
text
trampoline(factorial)(5)
→ factorial(5,1) → () => factorial(4,5)
→ trampoline 执行该函数 → factorial(4,5) → () => factorial(3,20)
→ 继续... 直到返回 120所有调用都在 trampoline 的 while 循环内完成，栈深度始终为 1。
五、更复杂的递归：树遍历
问题：非尾递归无法直接蹦床
js
const sumTree = node =>
!node ? 0 :
node.value + sumTree(node.left) + sumTree(node.right);这不是尾递归，因为有两个递归调用，且需相加。
解法：显式使用栈（模拟递归）
js
function sumTreeIterative(root) {
const stack = [root];
let total = 0;
while (stack.length) {
const node = stack.pop();
if (node) {
total += node.value;
stack.push(node.right, node.left); // 后进先出
}
}
return total;
}将递归逻辑转化为迭代 + 显式栈，完全避免调用栈溢出。
六、现代替代方案
1. 使用生成器（Generator）处理大列表
js
function* range(n) {
for (let i = 0; i < n; i++) yield i;
}
[...range(10000)].reduce((a,b) => a+b, 0); // 惰性生成2. 使用 async/await + 队列（适用于异步递归）
js
async function processQueue(queue) {
while (queue.length) {
const item = queue.shift();
await process(item);
}
}七、工程实践建议
推荐使用递归当：
- 数据结构天然递归（树、图）
- 逻辑清晰，且输入规模小
- 用于教学或 DSL 设计
避免递归当：
- 输入可能很大（如用户提供的 n）
- 性能关键路径
- 团队不熟悉函数式
安全策略：
- 对大输入使用 trampoline
- 或改写为 显式栈的迭代版本
- 使用 惰性求值（如 generator）分批处理
结语：递归是“问题的自然表达”，但需工程化保护
它让你用数学定义代替控制流，但 JS 的运行时限制了它的自由。
尾递归本应是完美的优化，
但现实引擎的支持缺失，
迫使我们用 trampoline 或 显式栈 来“手动优化”。
这提醒我们： 函数式编程不仅是风格，更是对运行时环境的深刻理解。
当你写下 f(n) = n * f(n-1)，
你是在定义数学；
当你用 trampoline 保护它，
你是在驾驭现实。