【JavaScript】栈溢出与递归优化
关于栈溢出错误
函数调用会在内存形成一个 调用记录，又称 调用帧（call frame），保存调用位置和内部变量等信息，所有的调用帧存放在调用堆栈中。
在函数中调用函数会保存之前的调用栈数据，将新的调用帧入栈。
栈溢出错误常见于递归操作，函数不断地重复调用自身导致调用堆栈不断堆叠，在超出浏览器限制的调用堆栈大小时抛出栈溢出错误 Uncaught RangeError: Maximum call stack size exceeded
递归优化
以阶乘函数为例：
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1); // 返回了一个函数调用与变量的表达式
}
尾递归
此方案大部分浏览器不支持。
尾递归的优化方式依赖于 ES 的 尾调用优化 方案。
尾调用就是指某个函数的最后一步是调用另一个函数，由于这是当前函数的最后一步操作，所以不需要保留外层函数的调用帧，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用帧，取代外层函数的调用帧就可以了。
尾递归方式改写：
function factorial(n, total = 1) {
if (n === 1) return total; // total为计算值也是最后的返回值
return factorial(n - 1, n * total); // 返回了一个函数调用
}
自己实现尾递归
浏览器对尾递归的支持性并不好，想在正常环境下使用尾递归优化就需要自己实现尾递归。
原理：使用 循环 替换 递归。
- 改写递归函数，让递归函数每次返回一个新函数。
- 添加一个新的
蹦床函数，用来执行递归函数返回的函数。
这里改写后就变成了每次执行函数就返回一个新函数，然后执行该函数，而不是在函数里面调用函数，这样就避免了递归执行，从而就消除了调用栈过大的问题。
迭代方式改写：
function trampoline(f) {
while (f && f instanceof Function) {
f = f();
}
return f;
}
function factorial(n, total = 1) {
if (n === 1) return total; // total为计算值也是最后的返回值
return factorial.bind(null, n - 1, n * total); // 返回了一个函数调用
}
trampoline(factorial(20000));
使用缓存&分批迭代
当递归函数被多次调用时，它其实做了很多重复的工作：
var fact6 = factorial(6);
var fact5 = factorial(5);
var fact4 = factorial(4);
以上代码生成三个阶乘结果，factorial() 函数总共被调用了 18 次。此代码中最糟糕的部分是，所有必要的计算已经在第一行代码中执行过了。
因为 6 的阶乘等于 6 乘以 5 的阶乘，所以 5 的阶乘被计算了两次。更糟糕的是，4 的阶乘被计算了三次。
更为明智的方法是保存并重利用它们的计算结果，而不是每次都重新计算整个函数。
function factorial(n) {
if (!factorial.cache) {
factorial.cache = {
0: 1,
1: 1,
};
}
if (!factorial.cache.hasOwnProperty(n)) {
factorial.cache[n] = n * factorial(n - 1);
}
return factorial.cache[n];
}
在使用缓存之后递归操作遇到已计算过的值时直接读缓存，不会重新调用函数计算，也就不会产生新的调用帧。
比如直接调用 factorial(1000000) 会导致栈溢出，那么只要先缓存小于 1000000 数值阶乘的缓存值，再调用 factorial(1000000) 就不会栈溢出了。
function splitFactorial(n) {
// 不会导致栈溢出的执行次数
let securityCount = 100;
// 需要执行多少次才能执行完毕
let loopAmount = Math.ceil(n / securityCount);
// 少执行一次，余数必然少于securityCount，直接在最后return即可
for (i = 1; i < loopAmount; i++) {
factorial(i * securityCount);
}
return factorial(n);
}
splitFactorial(1000000);
参考
高性能 JavaScript 编程