【每日一题】- 2020-06-28 - 尾递归优化

azl397985856 commented 4 years ago

如下代码可以正常返回。

function factorial(n) {
    if (n === 1) {
         return n
    }
    return n + factorial(n - 1)
}
factorial(10000)

如下代码会栈溢出。

function factorial2(n, total = 1) {
    if (n === 1) {
         return total
    }
    return factorial2(n - 1, total + n)
}
factorial2(10000)

为什么会这样呢？

azl397985856 commented 4 years ago

背景

实际上尾递归优化是ES6规范中一项。并且浏览器支持极差，详情可见：http://kangax.github.io/compat-table/es6/

可以看出：

chrome 85 桌面版没有进行支持，Edge 81 和 Edge 83 等少数浏览器进行了支持。（真是少见）
尾递归有两项：direct recursion 和 mutual recursion，浏览器目前对其是要么全部实现，要么全部不实现。

关于尾递归的详细规范描述参考：http://www.ecma-international.org/ecma-262/6.0/#sec-tail-position-calls

简单来说，就是如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。

也就是说上面的两种代码形式都是尾递归。

说明

尾递归和尾递归优化是两码事。尾递归是一种写法，尾递归优化是引擎做的事情。 具体来说就是对尾递归调用形式，不直接 append 到栈顶，而是先 pop 调当前的栈，再 append 到栈顶。

尾递归优化由于存在栈丢失，因此追踪问题可能变得更加困难，这也是尾递归迟迟没有推广的原因之一。

回到题目

实际上第一种和第二种在目前的 chrome 版本上是都不会进行尾递归优化的。只不过第二种在堆栈上会占用额外的空间，因此相同数据规模，第二种写法占用内存更大。而在规模为10000 的时候，恰巧第二种达到了 V8 的堆栈上界。你可以将一种代码的数据规模调大100倍看看效果。如果存在尾递归优化，那么无论调大多少倍，都不会爆栈才对。

测试

我们使用 node 进行测试，调整最大堆栈大小。

 node --stack-size=100 a.js

node 低版本是 --max-stack-size

a.js 就是上面的代码一，具体内容如下：

function factorial(n) {
  if (n === 1) {
    return n
  }
  return n + factorial(n - 1)
}
factorial(10000)

上面的代码会爆栈，当我们的数据规模变小的时候（比如10），才正常返回。

suukii commented 4 years ago

[絮絮念：不算答案，刚好写了一点笔记就贴一下吧]

虽然尾调用优化是 ES6 规范中的一部分，但其实大部分 JS 引擎都没有实现。

什么是尾调用优化？

正常情况下代码执行时，如果执行到一个函数，就会创建一个执行上下文推入到执行栈中，等到函数执行结束后再将这个执行上下文出栈。

如果我们在一个函数中调用了另一个函数，执行上下文就会在执行栈中一个一个摞起来。

下面是一个简单的递归：

const recursive = (n) => {
  if (n < 0) return
  console.log(n)
  recursive(n - 1)
}
recursive(10000)

在执行这段代码的时候，JS 引擎会不断地创建新的 recursive 执行上下文并推入执行栈中，如果 n 足够大，执行栈的内存空间最终会被用完并抛出栈溢出错误。

recursive_call_stack

如果我们仔细观察下上面的代码，会发现在调用了 recursive(n - 1) 之后，recursive(n) 的执行上下文其实已经没用了。因为在 recursive(n - 1) 这个操作之后，已经没有别的代码需要用到 recursive(n) 上下文中的任何变量了。那么，recursive(n) 的执行上下文其实没必要等到 recursive(n - 1) 执行完毕之后再出栈，而是在调用 recursive(n - 1) 的时候就可以出栈了，这就是尾调用优化。

recursive_call_stack_tco

尾调用优化的实现

V8 曾经实现过尾调用优化，但后来又放弃了，主要是因为实现尾调用优化意味着要在代码执行的过程中修改调用栈，这样的话，执行流的信息就不完整了，而且还会导致两个问题：

debug 的时候调用栈信息不完整
error.stack 的信息会不完整

鉴于这些原因，V8 团队建议修改规范，把 PTC(Proper Tail Calls) 改为 STC(Syntatic Tail Calls)，也就是要用特定的语法来使用尾调用，比如 return continue func()。目前 V8 还是不支持的，曾经它提供了 --harmony-tailcalls 和 --harmony-explicit-tailcalls 来开启尾调用优化，不过后来又移除了。

如何分辨尾调用

https://2ality.com/2015/06/tail-call-optimization.html#checking-whether-a-function-call-is-in-a-tail-position

azl397985856 / fe-interview