尾递归(TCO)

[msforest]

递归表示函数调用自身；尾递归表示函数 return 表达式调用自身函数；而尾递归优化(TCO)是解决调用栈溢出的问题，js 解析器为防止函数无线调用，通常会设置一个最大调用次数。如下面这段代码：

function f(n, total) {
  if (n === 1) return total;
  return f(n - 1, n + total);
}

当 n 足够大时，某些浏览器或 node 会抛出调用栈溢出的错误。

我们多多少少了解一些尾递归的概念，然而对于尾递归(优化)到底有什么用呢 ❓

递归调用是一种线性调用，在内存中会保存当前调用函数的信息；如：f(x1) -> f(x2) -> f(x3)，它的线性调用栈如图：

空间复杂度为 O(n)。如果实现尾递归优化，那么在栈中，函数调用栈会共用，空间复杂度为 O(1)，因此对内存消耗起到了一定作用。

严格模式
尾递归优化只在严格模式下有效。这是因为在正常模式下，函数内部有两个变量，可以跟踪函数的调用栈。

• arguments：返回调用时函数的参数。
• func.caller：返回调用当前函数的那个函数。

尾调用优化发生时，函数的调用栈会被改写，因此上面两个变量就会失真。严格模式禁用这两个变量，所以尾调用模式仅在严格模式下生效。

点击查看实现 TCO 的浏览器支持情况，很遗憾 chrome 浏览器未实现TCO

参考：

• 函数的扩展