在编程中使用递归,如果没有控制好代码的执行边界或过多层级的递归调用,就会造成栈溢出错误,就像下面展示的这段错误堆栈。
RangeError: Maximum call stack size exceeded
at fn (/xxx/test.js:2:3)
at fn (/xxx/test.js:7:10)
为什么递归会造成堆栈溢出?
函数运行会有一个执行栈,每次调用会做入栈操作,保存一些局部变量、函数参数、当前程序的运行状态等,这些信息都会保存在栈空间里,而栈空间的存储是一段连续的内存地址,有大小限制。
以下是一段递归调用的简单示例。
function fn(i) {
i--;
if (i < 1) {
return;
}
return fn(i);
}
fn(20000);
以下通过 gif 动图展示了上述代码的执行过程,当在主线程上调用 fn 函数后,不断的做压栈操作,而栈空间也在不断的增加,直到达到最大的栈空间限制,程序报错 “Maximum call stack size exceeded”。
使用异步解决栈溢出问题
解决递归造成的栈溢出问题,一种方法是可以使用 JavaScript 中的异步任务,也是借助了事件循环机制。宏任务有 setTimeout、Node.js 环境下的 setImmediate,微任务有 Promise、queueMicrotask。
修改代码,在 setTimeout 函数里递归调用。
function fn(i) {
i--;
if (i < 1) {
return;
}
setTimeout(function() {
fn(i);
}, 0);
}
fn(20000);
运行效果如下所示:
当首次调用 fn(2000) 时,创建一个调用栈,函数内部调用 setTimeout 函数后会立即返回,当前的调用栈就结束了,传入的回调 function() { fn(i) } 还没有执行,主线程不会在这里等待,也不会形成层层嵌套的调用链。
定时器函数由宿主环境实现,当将来的某个时间点计时器时间到达后,宿主环境会将 timer 函数封装为一个事件放入 “任务队列” 中,事件循环检测到任务队列有可执行的任务,就拿出来执行,之后再次调用 fn(i) 创建新的调用栈,反复循环。
还可以通过微任务实现,微任务有个缺点是当调度大量的微任务时虽然不会导致调用栈溢出,但也会导致和同步任务相同的性能缺陷,后面的任务得不到执行,浏览器的渲染工作也会被阻止,直到所有的微任务执行完毕。
总结
这个问题通过结合异步任务来解决递归造成的栈溢出问题,也可以做为事件循环的一个例子来学习,更好的掌握同步任务、异步之间的调度关系。
在程序中使用递归还是要谨慎的,若控制不好边界,很容易造成 “栈溢出”。除了改为异步任务调用外,还可将递归改为循环迭代、尾递归优化等。
版权声明:本文由[五月君]发表于
编程界