articles>javascript-tail-call-optimization>
JS中的尾调用优化

JS中的尾调用优化

ES6 新增了一个内存管理优化机制，让 JavaScript 引擎在满足条件时可以重用栈帧。

JavaScript
772字

什么是尾调用优化

ES6 新增了一个内存管理优化机制，让 JavaScript 引擎在满足条件时可以重用栈帧。

简单来说，就是 当外部函数的返回值是一个内部函数的返回值时，JS 引擎会自动优化。如：

javascript
function outerFunction() {
  function innerFunction() {
    return 1
  }
  return innerFunction()
}

在 ES6 优化之前，在内存中会发生：

  1. 代码执行到 outerFunction 函数体，第一个栈帧被推到栈上。
  2. 执行 outerFunction，到 return，必须先计算 innerFunction。
  3. 执行到 innerFunction，第二个栈帧被推到栈上。
  4. 执行 innerFunction，计算返回值。
  5. 返回值传给 outerFunction，然后 outerFunction 再返回值。
  6. 将栈帧弹出。

在 ES6 优化之后，在内存中会发生：

  1. 执行到 outerFunction 函数体，第一个栈帧被推到栈上。
  2. 执行 outerFunction，到 return，必须先计算 innerFunction。
  3. 引擎发现，把第一个栈帧弹出去也没问题，因为 innerFunction 的返回值也是 outerFunction 的返回值。
  4. 弹出 outerFunction 的栈帧。
  5. 执行到 innerFunction，栈帧被推到栈上。
  6. 执行 innerFunction，计算返回值。
  7. 弹出 innerFunction。

我们可以看到，在没有优化之前，每多调用一次嵌套函数，就会多增加一个栈帧。 而第二种情况，无论调用多少嵌套函数只有最后一个函数的栈帧。

如果函数的逻辑允许基于尾调用将其销毁，那么引擎就会这么做。

尾调用优化的条件

判断能够进行尾调用优化的条件就是 确定外部栈帧真的没必要存在了。

  • 代码在严格模式下执行
  • 外部函数的返回值是对尾调用函数的调用
  • 尾调用函数返回后不需要执行额外的逻辑
  • 尾调用函数不是引用外部函数作用域中自由变量的闭包

无论是递归尾调用还是非递归尾调用，都可以应用优化。 不过，这个优化在递归的时候最明显，因为递归会迅速产生大量栈帧。

为什么要求一定得是 'use strict' 呢？

因为在非严格模式下，函数允许使用 f.arguments 和 f.caller，而它们都会引入外部函数的栈帧。所以必须得在严格模式下确保这两个东西不能够被调用。

一些例子

我们平常写的斐波那契数列的递归代码可能是这样的：

javascript
function fib(n) {
  if (n < 2) {
    return n
  }
  return fib(n - 1) + fib(n - 2)
}

这段代码实际上 不符合尾调用优化，因为外层函数的返回是相加的操作的结果。

如果不优化，上面的代码的栈帧数的内存复杂度是 O(2^n)。

直观点，我们直接用 Node.js 来跑这段代码，令 n = 43。过了 43 之后几乎就跑不动了

可以看到花了 2.414s。

现在使用尾调用优化来重构这段代码：

javascript
'use strict'

function fib(n) {
  return fibImpl(0, 1, n)
}

function fibImpl(a, b, n) {
  if (n === 0) {
    return a
  }
  return fibImpl(b, a + b, n - 1)
}

这个重构的原理比较简单，每次递归都让前一个的 a + b 作为下一次递归的 b，实现逐层累加的效果。

我们同样用 n = 43 跑跑：

几乎就是一瞬间。那么，我们换更大的又如何呢？

我们用 n = 1000 来跑跑：

几乎耗时是一样的。因为在递归最后的栈帧，只有一个函数。这就是尾调用.jpg

评论0