提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

有趣-如何解决递归过多导致的栈溢出

递归 如何 解决 导致 溢出 有趣 过多
2023-09-14 09:13:41 时间

这个问题是从B站一个UP主那边分享过来的，前端大厂实习面经系列-字节跳动篇 头条前端 面试_哔哩哔哩_bilibili

感觉问题很新颖，按照以前的思路递归过多就不递归喽，但是这里是强制递归实现，UP主提供了一种解决思路，给我打开了一个新世界大门。

另外评论区也是有大神的，给出我开了其他的大门，大家有兴趣可以去看看。

我们知道函数递归，就是函数自己调用自己，而每次函数调用就会产生一个函数执行上下文（栈帧）入执行栈，所以递归函数都依赖于下一个递归函数调用结束来实现自己实现结束调用而出栈，如果递归函数没有结束方向的话，就会发生执行栈内存不够分配，导致执行栈中栈帧溢出。

但是这里问题是递归过多，而不是递归没有结束方向。

递归过多是指，递归有结束方向，但是在结束之前就发生了栈溢出。

function sum(total, i) {
    if(i === 0) { // 递归结束条件
        return console.log(total)
    }
    sum(total+i, i-1) // 递归
}

sum(0,10)
sum(0,100)
sum(0,1000)
sum(0,10000) // 栈溢出

这里有什么方法解决呢？而且必须使用函数递归，不能改用for循环。

我们需要知道事件循环模型，即JS运行时内存图

我们需要知道除了执行栈可以通过存放函数外，还有一个地方可以存放函数，那就时异步任务队列中 ，该队列一般用于存储 异步任务的回调函数，等待执行栈只有全局执行上下文时，就会因为Event Loop而被JS主线程取出放入执行栈中执行。

这样就可以达到将递归函数从执行栈中转移到异步队列中，从而减轻执行栈压力的目的。

function sum(total, i) {
    if(i === 0) { // 递归结束条件
        return console.log(total)
    }
    setTimeout(sum,0, total+i, i-1) // 注意这里给sum直接传参会触发sum立即执行，而不是回调执行
}

sum(0,10)

但是出现了一个新问题，结果输出耗时太长。这是为啥呢？

首先，sum(0,10)调用，进入执行栈，函数执行到setTimout，将回调函数sum交给webAPI线程处理，之后sum(0,10)函数调用结束出栈。

需要注意的时 setTimeout设置0s等待，并不是真的0s等待，setTimeout有个最小延迟时间，下面是MDN的描述

也就是说，setTimeout会等待4ms后，再将回调sum加入异步任务队列，而JS主线程通过时间循环从异步任务队列取出回调函数sum也需要时间，所以每次递归函数sum都要经过不少于4ms的时间才可能被加入执行栈执行，

比如 sum(0,10) 就需要不少于 9*4ms = 36ms

        sum(0,100) 就需要不少于 360ms, 0.36s

        sum(0,1000) 就需要不少于 3600ms, 3.6s

        sum(0,10000) 就需要不少于 36000ms，36s

实际情况，肯定比预估时间长

所以我们不能一味的将sum递归函数扔到异步任务队列中。

我们可以让 执行栈先存入部分递归函数调用，当快要到执行栈临界值时，我们就将下次递归函数调用交给异步任务队列，这样就能达到清空执行栈的目的，然后等待4ms左右再将递归函数加入执行栈执行，等到快要到临界值时，再加入异步任务队列以清空执行栈

关于上面红字部分，为什么将下次递归函数加入异步任务队列，就能达到清空执行栈的目的呢？

因为加入异步任务队列的递归函数，不会立即执行，而是需要等待执行栈中的同步任务执行完后，才能被主线程调用加入执行栈中执行。

这里会产生两个影响：

1、被加入异步任务队列的递归函数不会立即执行，因此不会再产生新的递归调用。

2、执行栈中同步调用的递归函数优先执行，因此达到了清空执行栈的目的。

比如当前执行栈临界值小于 10000 大于 1000，我们就让临界值为1000，

这样sum(0,10000) 只需要不少于 (10000 / 1000) * 4ms  = 40ms 就可以全部完成了。

function sum(total, i) {
    if(i === 0) { // 递归结束条件
        return console.log(total)
    }
    if(i%1000 === 0) {
        setTimeout(sum,0, total+i, i-1)
    } else {
        sum(total+i, i-1)
    }
}

 

这样速度就上去了 

那有没有可能继续优化？我们再来看下这个JS运行图

当前是将递归函数通过setTimeout加入异步宏任务队列，但是加入异步宏任务队列有几个缺点

1、setTimeout将递归函数加入异步宏任务队列，需要等待至少4ms，有延迟

2、一次事件轮询只能从异步宏任务队列中取出一个递归函数来执行，事件轮询也需要时间

如果将递归函数加入异步微任务队列，就可以解决该缺点

1、加入异步微任务队列没有时间延迟

2、一次事件轮询就可以处理异步微任务队列中所有递归函数

function sum(total, i) {
    if(i === 0) { // 递归结束条件
        return console.log(total)
    }
    if (i%1000 === 0) {
        Promise.resolve().then(sum.bind(null,total+i,i-1))
    } else {
        sum(total+i,i-1)
    }
}

这样速度就能快一点了

上面这些解决方案其实都是依赖于JS的运行机制中的异步队列，是具有JS特色的解决方案。但是有没有一种正规军打法呢？

那就是尾递归函数的扩展 - ECMAScript 6入门 (ruanyifeng.com)

  我们来用尾递归优化下上面代码

function sum(total, i) {
    if(i === 0) {
        return total
    }
    return sum(total+i, i-1)
}

但是发现并没有解决递归过多问题，那是因为目前很多浏览器还不支持尾递归

ECMAScript 6 compatibility table (kangax.github.io)

Chrome和Edge还不支持

 Nodejs也不支持

相关文章