JavaScript 你必须要知道的尾递归调用及尾调用优化

2021-04-24

ptc
通常，在一个函数内部调用另一个函数的时候，会分配第二个栈帧来独立管理第二个函数调用的变量、状态。这个分配不但消耗处理时间也消耗了额外的内存。

尾递归调用

通常调用栈链最多有10 ~ 15 个从一个函数到另一个函数的跳转。这种情况下，内存使用并不会造成任何实际问题。
但是，当考虑到递归编程的时候，或者两个或多个函数彼此调用形成递归，调用栈的深度很容易刀刀成百上千甚至更多。如果内存的使用无限制的增长下去，就会遇到内存溢出。

JavaScript 引擎不得不设置一个限制来防止这种编程技术引起浏览器和设备内存耗尽而崩溃。这也是为什么达到这个限制的时候我们会得到烦人的“RangeError: Maximum call stack size exceeded.”

调用栈的深度限制不由规范控制。它是依赖于具体情形实现的，并且根据浏览器和设备不同而有所不同。在编码的时候不要对观察到的具体限制值有任何强假定，因为他很有肯呢过根据发布版本的不同而变化。

有一些称为尾调用（tail call）的函数调用模式，可以以避免额外栈帧分配的方式进行优化，如果可以避免额外的分配，就没有理由人以限制调用栈深度，所以引擎就可以不设置这个限制了。

尾调用是一个 return 函数调用的语句，除了调用后返回其返回值之外没有任何其他动作。

这个优化只在 strict 模式下应用。这又是一个要坚持编写 strict 模式代码的原因！

下面是一个不在尾位置的函数调用：

"use strict"

function foo(x) {
  return x * 2;
}

function boo(x) {
  // 这不是尾调用！
  return 1 + foo(x);
}

boo(10); // 21

foo(x)调用完毕后还得执行 1 + ... ，所以 boo(...) 调用的状态需要被保留。

但下面的代码展示的对 foo(...) 和 boo(...) 的调用都处于尾位置，因为他们是在其代码路径上发生的最后一件事（除了 return);

"use strict"

function foo(x) {
  return x * 2;
}

function boo(x) {
  x = x + 1;
  if (x > 10) {
    return foo(x);
  }
  return boo(x + 1);
}

boo(5); // 24
boo(15); 32

在这个过程中，boo(...) 显然是递归，而 foo(...) 只是一个普通函数调用。在这两种情况下，函数调用都处于合适的尾位置。 x + 1 在 boo(...) 调用之前求值，在调用结束后，所做的就只有 return 。

这些形式的正确尾调用（Proper Tail Call，PTC）是可以被优化的，成为尾调用优化（Tail Call Optimization， TCO），于是额外的栈帧分配是不需要的。引擎不需要对下一个函数调用创建一个新的栈帧，只需复用已有的栈帧。者能够工作是因为一个函数不需要保留任何当前状态 —— 在PTC之后不需要这个状态做任何事情。

TCO 意味着对调用栈的允许深度没有任何限制。对于一般程序中的普通函数调用，这个技巧有些许优化，但更重要的是打开了在程序表达中使用递归的大门，甚至是调用栈的调用深度可能达到成千上万的时候。

现在我们不再只把递归作为解决问题的理论方案了，而是可以实际将其用在 JavaScript 程序中了！

对于 ES6 来说，不管是否为递归，所有的 PTC 都应该以这种方式优化。

尾调用重写

但这里的问题是只有 PTC 可以被优化，非 PTC 当然仍然可以继续运行，但是会像以前一样触发栈帧分配。如果你希望这个优化接入的话，需要认真设计函数结构支持 PTC。

如果有一个函数不是以 PTC 方式编写的，那么你可能需要手动重新调整代码意识和 TCO。

考虑：

"use strict"

function foo(x) {
  if (x <= 1) return 1;
  return (x / 2) + foo(x - 1);
}

foo(123456); // RangeError

调用 foo(x-1) 不是 PTC，因为它的结果每次在 return 之前都要加上 （x / 2）.

但是，要想使这段代码适合 ES6 引擎 TCO, 可以这样重写：

"use strict"

var foo = (function() {
  function_foo(acc, x) {
    if (x <= 1>) return acc;

    return _foo((x / 2) + acc, x - 1);
  }
  return function (x) {
    return _foo(1, x);
  };
  }
})();

foo(123456); // 3810376848.5

如果你在实现了 TCO 的 ES6 引擎中运行上面的代码，会得 3810376848.5 这个结果。然而，它在非 TCO 引擎里仍然会因 RangeError 而失败。

非 TCO 优化

还有几种其他技术可以用来重写代码，使得不需要每次调用时都增长栈。

其中一种叫做 trampolining(蹦床)，它相当于把每个部分结果用一个函数表示，这些函数或者返回另外一个部分结果函数，或者返回最终结果。然后就只需要循环直到得到的结果不是函数，得到的就是最终的结果。

"use strict"

function trampoline(res) {
  while (typeof res === 'function') {
    res = res();
  }
  return res;
}

var foo = (function() {
  function_foo(acc, x) {
    if (x <= 1) return acc;

    return function partial() {
      return _foo((x/2) + acc, x - 1);
    };
  }

  return function(x) {
    return trampoline(_foo(1, x));
  }
})();

foo(123456);  // 3810376848.5

这个重写需要最小的改动来把递归转化为 trampoline(...) 中的循环。

首先，把 return _foo ... 一行封装在 return partial() { ... 函数表达式中。
然后，把 _foo(1, x) 调用封装在 trampoline(...) 调用中。

这个技术不限制调用栈的原因是，每个内部的 partial(...) 函数只是返回到 trampoline(...) 的 while 循环中， trampolining 运行函数并进行下一次的循环迭代。换句话说，partial(...) 不会递归调用资深，他只是返回另一个函数，栈深度不变了，所以可以运行任意长的时间。

通过这种方式实现的 trampolining 使用了内层 partial(...) 函数在变量 x 和 acc 上的闭包，在迭代之间保持状态。其优点是把循环逻辑抽出到了可复用的 trampoline(...) 工具函数，很多库都提供了他的各种版本。可以在你的程序中用不同的 trampoline 算法多次复用 trampoline(...)；

当然，如果真的需要深度优化（不需要考虑复用性），那么可以丢地闭包状态，用一个循环把 acc 信息的状态追踪在线化放在一个函数作用域内，这种技术一般称为递归展开：

"use strict"

function foo(x) {
  var acc = 1;
  while (x > 1) {
    acc = (x / 2) + acc;
    x = x - 1;
  }

  return acc;
}

foo(123456); // 3810376848.5

算法的这种表达方式可读性更高，很可能也是我们前面探索的各种形式中性能最高的。所以这个方案显示是最好的，你可能会奇怪那为什么我们还要用其他方法。下面是两个使用我们并不想总是手动展开递归的原因：

这里没有为了可复用性把 trampolining （循环）逻辑提取出来，而是将它在线化了。在只需要考虑一个例子的时候还合适，但是如果你的程序中有多个这种情况，很可能需要提高复用度来保持diamante更简短，更易管理。
这里的例子非常简单，只是用来展示各种不同的形式。但是在具体业务实践中，递归算法中还有很多更复杂的逻辑，比如互相递归（不只是一个函数调用自身）。

对这个无底洞探索越深，就会发现展开优化变得越手动化和错综复杂。你很快就会丧失所有前面得到的可读性价值。递归的最主要又是，即使是 PTC 形式，就是它保留了算法的可读性，并将性能优化的担子扔给了引擎。

如果以 PTC 的形式编写算法， ES6 引擎就会应用 TCO，代码就会以常数栈深度运行。你在得到递归的可读性的同事，也得到了了几乎没有损失的性能以及不受限制的运行长度。

JavaScript 你必须要知道的尾递归调用及尾调用优化

尾递归调用

尾调用重写

非 TCO 优化

上一页

JavaScript 设计模式介绍及其在业务中的应用

设计模式

下一页

从一道题目探究promise的使用技巧

JS

评论