20. 了解过尾递归优化吗
总结
- 尾递归（Tail Recursion） 是一种特殊的递归形式，函数的最后一步仅返回递归调用的结果。
- 在严格模式下，ES6 引入了尾调用优化（Tail Call Optimization, TCO），可以避免递归调用栈无限增长，从而优化性能和内存使用。
- 尾递归优化不是所有 JavaScript 引擎都支持，使用时需注意兼容性。
什么是尾调用（Tail Call）？
如果一个函数的最后一步仅仅调用另一个函数并返回其结果，则该调用称为尾调用。
function f(x) {return g(x); // ✅ 尾调用
}
function f(x) {const result = g(x);return result; // ✅ 也是尾调用
}
function f(x) {return g(x) + 1; // ❌ 不是尾调用（最后一步是加法）
}
function f(x) {return g(x) || h(x); // ❌ 不是尾调用（最后一步是逻辑运算）
}
什么是尾递归（Tail Recursion）？
当函数递归调用自身并且该调用是尾调用时，称为尾递归。
function factorial(n, acc = 1) {if (n <= 1) return acc;return factorial(n - 1, n * acc); // ✅ 尾递归
}
对比普通递归：
function factorial(n) {if (n <= 1) return 1;return n * factorial(n - 1); // ❌ 非尾递归（最后一步是乘法）
}
尾递归优化的优势
- 避免栈溢出（Stack Overflow）：普通递归会不断压栈，容易造成栈溢出。
- 减少内存占用：尾递归优化后，调用栈不会无限增长。
- 提升性能：减少函数调用带来的额外开销。
如何实现尾递归优化？
- 确保是尾调用：递归调用必须是函数的最后一个操作。
- 使用累加器（Accumulator）：将中间结果通过参数传递，避免在栈中保存状态。
// 普通递归（非尾递归）
function sum(n) {if (n <= 0) return 0;return n + sum(n - 1);
}// 尾递归版本
function sum(n, acc = 0) {if (n <= 0) return acc;return sum(n - 1, n + acc);
}
尾递归优化的兼容性
| 引擎/环境 | 是否支持尾调用优化 |
|---|---|
| V8（Chrome） | ❌ 不支持（出于调试考虑） |
| SpiderMonkey（Firefox） | ✅ 支持部分尾调用优化 |
| JavaScriptCore（Safari） | ✅ 支持 |
| Node.js（基于 V8） | ❌ 不支持 |
⚠️ 注意：即使在支持尾调用优化的环境中，也必须在 严格模式（‘use strict’） 下才能生效。
最佳实践建议
- ✅ 使用尾递归时，尽量使用累加器模式。
- ✅ 在不支持尾递归优化的环境中，考虑使用 循环替代递归。
- ✅ 避免在大型递归中使用非尾递归，防止栈溢出。
- ✅ 使用 Babel 等工具进行编译优化，自动将递归转换为循环。
示例：尾递归与普通递归对比
普通递归（易栈溢出）
function fib(n) {if (n <= 1) return n;return fib(n - 1) + fib(n - 2);
}
尾递归版本
function fib(n, a = 0, b = 1) {if (n === 0) return a;return fib(n - 1, b, a + b);
}