为何异步任务能解决递归栈溢出？

在编程中使用递归，如果没有控制好代码的执行边界或过多层级的递归调用，就会造成栈溢出错误，就像下面展示的这段错误堆栈。

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-recursion-stack-overflow.gif

使用异步解决栈溢出问题

解决递归造成的栈溢出问题，一种方法是可以使用 JavaScript 中的异步任务，也是借助了事件循环机制。宏任务有 setTimeout、Node.js 环境下的 setImmediate，微任务有 Promise、queueMicrotask。

修改代码，在 setTimeout 函数里递归调用。

function fn(i) {
  i--;
  if (i < 1) {
    return;
  }

  setTimeout(function() {
    fn(i);
  }, 0);
}

fn(20000);

运行效果如下所示：

javascript-async-recursion.gif

当首次调用 fn(2000) 时，创建一个调用栈，函数内部调用 setTimeout 函数后会立即返回，当前的调用栈就结束了，传入的回调 **function() { fn(i) }** 还没有执行，主线程不会在这里等待，也不会形成层层嵌套的调用链。

定时器函数由宿主环境实现，当将来的某个时间点计时器时间到达后，宿主环境会将 timer 函数封装为一个事件放入 “任务队列” 中，事件循环检测到任务队列有可执行的任务，就拿出来执行，之后再次调用 fn(i) 创建新的调用栈，反复循环。

还可以通过微任务实现，微任务有个缺点是当调度大量的微任务时虽然不会导致调用栈溢出，但也会导致和同步任务相同的性能缺陷，后面的任务得不到执行，浏览器的渲染工作也会被阻止，直到所有的微任务执行完毕。

总结

这个问题通过结合异步任务来解决递归造成的栈溢出问题，也可以做为事件循环的一个例子来学习，更好的掌握同步任务、异步之间的调度关系。

在程序中使用递归还是要谨慎的，若控制不好边界，很容易造成 “栈溢出”。除了改为异步任务调用外，还可将递归改为循环迭代、尾递归优化等。

- END -