递归调用栈溢出问题分析与解决

问题模拟

让递归爆栈还是很简单的，例如如下代码就能轻而易举实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 故意来一次爆栈体验
function stackOverflow(){
    stackOverflow()
}
stackOverflow()
// 结果
VM42:3 Uncaught RangeError: Maximum call stack size exceeded
    at stackOverflow (<anonymous>:3:5)
    at stackOverflow (<anonymous>:3:5)
    at stackOverflow (<anonymous>:3:5)
    at stackOverflow (<anonymous>:3:5)
    at stackOverflow (<anonymous>:3:5)
    at stackOverflow (<anonymous>:3:5)
    at stackOverflow (<anonymous>:3:5)
    at stackOverflow (<anonymous>:3:5)
    at stackOverflow (<anonymous>:3:5)
    at stackOverflow (<anonymous>:3:5)

我们还能通过如下代码看到浏览器最大的调用栈是多少

1
2
3
4
5
6
7
8
9
10
(function getStackDepth(){
    try {
        return 1 + getStackDepth()
    } catch (e) {
        // Call stack overflow
        return 1
    }
})()
// 结果
12539

数量取决于方法体所占用的空间，占用空间越大，可用栈数量越小。可尝试在方法中增加变量，会发现结果变小。

原因分析

我们都知道，程序运行时有堆内存，还有栈内存。
每一次方法执行，都会把方法压到执行栈中。
栈空间是有大小的，当超过栈空间大小，就会触发Maximum call stack size exceeded异常。

关于调用栈之前的这篇文章中有说明：CodeReview过程中关于JS代码性能的随想整理

解决方案

有了原因分析，解决方案也清晰了，那就是想办法规避掉不停的往调用栈塞方法。

样例准备

准备一个相加的例子（这个例子不具备实际意义，本来想准备个阶乘的例子，发现还没爆栈就超出整形长度了，累加也一样，所以就出现了这么一个看起来有点脑残的样例…）

1
2
3
4
5
6
7
8
// 用递归实现相加，比如输入add(10),打印10
function add(num){
  if(num===1){
    return 1
  }else{
    return 1 + add(num-1)
  }
}

可以看到，参数比较小的时候一切正常，当参数太大的时候就爆栈了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
add(10)
// 10
add(100000)
// 提示爆栈
VM505:2 Uncaught RangeError: Maximum call stack size exceeded
    at add (<anonymous>:2:3)
    at add (<anonymous>:5:16)
    at add (<anonymous>:5:16)
    at add (<anonymous>:5:16)
    at add (<anonymous>:5:16)
    at add (<anonymous>:5:16)
    at add (<anonymous>:5:16)
    at add (<anonymous>:5:16)
    at add (<anonymous>:5:16)
    at add (<anonymous>:5:16)

递归转循环

大部分递归都可以转为循环实现

1
2
3
4
5
6
7
8
9
10
function add(num){
  let result = 0
  while(num--){
    result = result+1
  }
  return result
}
add(100000)
// 正常输出100000
// 100000

蹦床函数

爆栈的核心在于不停的往调用栈塞入函数，那么我们可以想办法每次递归都执行对应函数，避免调用栈增加

  • 对递归改写

    1
    2
    3
    4
    5
    // 每次返回函数
    function add(num, result=1){
      if(num===1) return result
      return ()=> add(num-1, 1+result)
    }

  • 蹦床函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    function trampoline(fun){
      let result = fun()
      // 循环调用，解决递归问题
      while (typeof(result)==='function') {
        result = result()
      }
      return result
    }

    trampoline(add(100000))
    // 返回100000

事件

最后还有一个sao操作，就跟传说中的睡眠排序一样，那就是setTimeout，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
function add(num, result=1){
  return new Promise((resolve, reject)=>{
    if(num===1) resolve(result)
    // 实际上为最少4ms执行一次
    setTimeout(function(){
      add(num-1, 1+result).then(res=>resolve(res))
    }, 0)
  })
}
// 能够正常返回100，参数为15000时，也能返回值(证明不会爆栈)，就是巨慢...
add(100).then(res=>console.log(res))

相关文章

如何避免 JavaScript 长递归导致的堆栈溢出？
How to avoid Stack overflow error on recursion
CodeReview过程中关于JS代码性能的随想整理

留言

欢迎交流想法。留言会通过 GitHub Issues 保存，首次使用需要登录 GitHub。