• 主页
  • 随笔
所有文章 友链 关于我

  • 主页
  • 随笔

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

2020-08-27

问题模拟

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

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代码性能的随想整理

赏

谢谢你请我吃糖果

扫一扫,分享到微信

微信分享二维码
如何做好一线团队管理?
模拟koa洋葱模型实现
© 2025 YiYing
Hexo Theme Yilia by Litten
  • 所有文章
  • 友链
  • 关于我

tag:

  • 读书笔记
  • sql注入
  • sqlmap
  • nexus
  • HTTP安全
  • restfull
  • 随笔
  • 哲学
  • 缓存
  • HTTP状态码
  • HTTP连接
  • RSA
  • Java
  • JavaScript
  • 安全
  • 排序算法
  • POI
  • 工具类
  • 工作思考
  • Life
  • 读书
  • 前端
  • 团队管理

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

  • 友情链接1
  • 友情链接2
  • 友情链接3
  • 友情链接4
  • 友情链接5
  • 友情链接6
很惭愧

只做了一点微小的工作
谢谢大家