0%

面试官问:怎么避免函数调用栈溢出

前言

基友最近遇到的一道面试题

1
2
3
4
5
6
7
8
9
10
11
/** 
* 输出 n->0
*/
function foo(n){
console.log(n)
if(n > 0){
foo(n - 1)
}
}
foo(100000)
// 请问输出什么

答案很简单,栈溢出呗。解决方法也很简单,递归改迭代咯。

正常来说,这个问题就应该结束了。。那要是面试官再这样问你 –

那你知道函数执行栈的上限么

在没看过 v8 配置的情况下可以这样测试

1
2
3
4
5
6
7
8
function c(){
try {
return 1 + c()
} catch(e){
return 1
}
}
c()

测试结果:

  • win7x64 chrome74:25173
  • win7x64 chrome81: 12571
  • mbp chrome80: 12547
  • mbp chrome81: 12540
  • mbp Safari13: 36244

可以发现,不同的执行引擎,执行引擎的不同版本,不同的设备配置都会影响栈的深度

在明白这点之后我们再看这个例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function c(){
let arr = new Array(10000).fill(1)
try {
let res = c() + arr[999]
// 无用代码
if(res < 0){
for(let i=0;i<arr.length;i++){
res+=arr[i]
}
}
return res
} catch(e){
return 1
}
}
c()

在 win7x64 chrome81 得到的结果为: 9669

可以发现,调用栈的深度取决于调用函数的函数体大小和本地变量的个数

由于栈的容量(size)是固定的,其实更应该关注栈的容量,而不是栈的深度

在 Node.js 中,可以通过以下命令查看栈的容量

1
2
3
4
5
6
7
$ node --v8-options | grep stack-size -A 1
--stack-size (default size of stack region v8 is allowed to use (in kBytes))
type: int default: 984
--
--sim-stack-size (Stack size of the ARM64, MIPS64 and PPC64 simulator in kByte
s (default is 2 MB))
type: int default: 2048

win7x64 和 mbp 的 Node.js 12 输出均一致,默认栈大小为 984KB

我们可以在运行时指定栈的大小来防止栈溢出,还是上面那个例子,在 node.js 上测试:

1
2
3
4
5
6
function foo(n){
if(n > 0){
foo(n - 1)
}
}
foo(20000)

直接执行 node a.js 会栈溢出,但是

1
node --stack-size=1968 a.js

则不会。

总的来说,在日常开发中,如果有数千的递归,就需要考虑重写优化了,否则有些平台将导致错误

听过尾调用和尾递归么

尾调用即在函数的最后一步调用另一个函数,而尾递归则是函数的最后一步调用自身

注意,最后一步需要是单个函数调用,以下代码均不是尾调用

1
2
3
4
5
6
7
8
9
10
11
12
function a(){
let t = b()
return t
}
function b(){
c()
// 等效于
// return undefined
}
function c(){
return d() + 1
}

使用尾调用和尾递归,可以避免中间无用的上下文(调用帧),仅保留最外层和当前层,避免栈溢出

题目要采用尾递归解决,怎么改

1
2
3
4
5
6
7
function foo(n){
'use strict';
console.log(n)
if(n > 0){
return foo(n - 1)
}
}

ES6 的尾调用优化只在严格模式下开启,主要原因在于正常模式下函数有两个变量可以跟踪函数的调用栈

  • func.arguments:返回调用时函数的参数
  • func.caller:返回调用当前函数的那个函数
    这两个变量在尾调用优化上的值与未优化的情况不一致,而严格模式下这两个变量是禁用的,这样可以保证调用栈的正确性

浏览器的兼容性怎么样

如果把上面那段代码放在 chrome 控制台执行,还是会报栈溢出。

我们可以看下尾调用优化的兼容性

可以看到主流浏览器基本上只有 Safari 支持,把上述那段代码放 Safari 上测试了下是可以通过的

所以在浏览器环境,还是不是想着利用尾递归来解决问题

Node.js 能使用尾递归么

在 node 6,7 可以通过 --harmony-tailcalls 开启,而在 8 之后删掉了这个选项。

所以可以理解为 Node.js 不支持尾递归

尾递归看着这么好,为什么这么多执行引擎不支持?

关于这个问题,V8 的这篇文章给出了答案

概括如下

1. 隐式优化问题

引擎消除尾调用是隐式的,程序员很难确定哪些函数实际上位于尾部调用位置,这导致了程序员在编码时得不断的调试才能写出正确的尾递归方法。

2. 栈帧丢失

尾调用会清除中间执行栈帧,导致 error.stack 中包含的有关执行流程的信息较少,进而影响依赖调用堆栈信息的调试和错误收集过程

STC 了解么?

STC 是为了解决尾调用优化不受开发者控制的问题,通过新的语法糖显式指定尾调用,比如 return continue foo(n-1)

在非尾调用的场景下使用该语法糖则会报错

具体的可以看 tc39 - proposal-ptc-syntax


拓展阅读

您的支持将鼓励我继续创作!