面试官问：怎么避免函数调用栈溢出
# 前言
基友最近遇到的一道面试题
/**
* 输出 n->0
*/
function foo(n){
console.log(n)
if(n > 0){
foo(n - 1)
}
}
foo(100000)
// 请问输出什么
2
3
4
5
6
7
8
9
10
11
答案很简单，栈溢出呗。解决方法也很简单，递归改迭代咯。
正常来说，这个问题就应该结束了。。那要是面试官再这样问你 --
# 那你知道函数执行栈的上限么
在没看过 v8 配置的情况下可以这样测试
function c(){
try {
return 1 + c()
} catch(e){
return 1
}
}
c()
2
3
4
5
6
7
8
测试结果：
- win7x64 chrome74：25173
- win7x64 chrome81: 12571
- mbp chrome80: 12547
- mbp chrome81: 12540
- mbp Safari13: 36244
可以发现，不同的执行引擎，执行引擎的不同版本，不同的设备配置都会影响栈的深度
在明白这点之后我们再看这个例子
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()
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
在 win7x64 chrome81 得到的结果为： 9669
可以发现，调用栈的深度取决于调用函数的函数体大小和本地变量的个数
由于栈的容量(size)是固定的，其实更应该关注栈的容量，而不是栈的深度
在 Node.js 中，可以通过以下命令查看栈的容量
$ 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
2
3
4
5
6
7
win7x64 和 mbp 的 Node.js 12 输出均一致，默认栈大小为 984KB
我们可以在运行时指定栈的大小来防止栈溢出，还是上面那个例子，在 node.js 上测试：
function foo(n){
if(n > 0){
foo(n - 1)
}
}
foo(20000)
2
3
4
5
6
直接执行 node a.js 会栈溢出，但是
node --stack-size=1968 a.js
则不会。
总的来说，在日常开发中，如果有数千的递归，就需要考虑重写优化了，否则有些平台将导致错误
# 听过尾调用和尾递归么
尾调用即在函数的最后一步调用另一个函数，而尾递归则是函数的最后一步调用自身
注意，最后一步需要是单个函数调用，以下代码均不是尾调用
function a(){
let t = b()
return t
}
function b(){
c()
// 等效于
// return undefined
}
function c(){
return d() + 1
}
2
3
4
5
6
7
8
9
10
11
12
使用尾调用和尾递归，可以避免中间无用的上下文（调用帧），仅保留最外层和当前层，避免栈溢出
# 题目要采用尾递归解决，怎么改
function foo(n){
'use strict';
console.log(n)
if(n > 0){
return foo(n - 1)
}
}
2
3
4
5
6
7
ES6 的尾调用优化只在严格模式下开启，主要原因在于正常模式下函数有两个变量可以跟踪函数的调用栈
- func.arguments：返回调用时函数的参数
- func.caller：返回调用当前函数的那个函数 这两个变量在尾调用优化上的值与未优化的情况不一致，而严格模式下这两个变量是禁用的，这样可以保证调用栈的正确性
# 浏览器的兼容性怎么样
如果把上面那段代码放在 chrome 控制台执行，还是会报栈溢出。
我们可以看下尾调用优化的兼容性 (opens new window)
可以看到主流浏览器基本上只有 Safari 支持，把上述那段代码放 Safari 上测试了下是可以通过的
所以在浏览器环境，还是不是想着利用尾递归来解决问题
# Node.js 能使用尾递归么
在 node 6,7 可以通过 --harmony-tailcalls 开启，而在 8 之后删掉了这个选项。
所以可以理解为 Node.js 不支持尾递归
# 尾递归看着这么好，为什么这么多执行引擎不支持？
关于这个问题，V8 的这篇文章 (opens new window)给出了答案
概括如下
# 1. 隐式优化问题
引擎消除尾调用是隐式的，程序员很难确定哪些函数实际上位于尾部调用位置，这导致了程序员在编码时得不断的调试才能写出正确的尾递归方法。
# 2. 栈帧丢失
尾调用会清除中间执行栈帧，导致 error.stack 中包含的有关执行流程的信息较少，进而影响依赖调用堆栈信息的调试和错误收集过程
# STC 了解么？
STC 是为了解决尾调用优化不受开发者控制的问题，通过新的语法糖显式指定尾调用，比如 return continue foo(n-1)
在非尾调用的场景下使用该语法糖则会报错
具体的可以看 tc39 - proposal-ptc-syntax (opens new window)