这是一个尾调用吗？（Javascript）

Question

假设你有一个递归函数如下：

Blah.prototype.add = function(n) {
    this.total += n;
    this.children.forEach(function(child) {
        child.add(n);
    });
};

child.add()是尾调用吗？如果不是，能否将其编写成尾调用形式?

- pixelmike

---

我不确定...我在考虑传统的for(i=0;i<children.length;i++)循环，并且认为n < children.length比较将是最后一个动作。不确定forEach是否适用，如果是这种情况，为什么forEach比for更受欢迎。 - pixelmike

在JS中，尾调用应该会使用return someFn()，这样还可以使得调用函数被垃圾回收。 - Roko C. Buljan

forEach() 在迭代时无法看到被推入数组的项目... - dandavis

这是在回调函数内部的尾调用，但“forEach”仍然需要保持其循环状态。因此，在这种情况下，在堆栈使用方面实际上几乎没有和“for”循环之间的区别。 - Barmar

@pixelmike 如果你不确定的话，可以将其重写为迭代算法 ;) - plalx

Answer 1

是的，这是一个尾调用：

function(child) {
    child.add(n);
// ^ tail
}

然而，这里没有尾递归，因为它不是直接递归调用。

此外，在add方法内部，this.children.forEach(…)是一个尾调用。

然而，原生的forEach方法内部回调函数的调用可能没有进行尾调用优化（并且除了最后一个之外的所有调用都无法进行优化）。您可以通过重写函数来强制进行优化。

Blah.prototype.add = function(n) {
    "use strict";
    this.total += n;
    let l = this.children.length;
    if (!l--)
        return;
    for (let i=0; i<l; i++)
        this.children[i].add(n);
    this.children[i].add(n); // tail-recursion
};

请注意，如果您不同时返回这些尾调用的结果，则不会对它们进行优化。

- Bergi

---

你确定add是尾递归吗？即使使用了简单的for循环结构，最后执行的操作也将是循环条件检查，因此不会是尾递归，对吗？我认为递归调用必须是算法中最后执行的表达式才能称为尾递归。 - plalx

@plalx：我没有说add是尾递归的。如果它与forEach及其回调函数相互递归，那么它不会调用自身。我只是说add包含一个尾调用。 - Bergi

谢谢，是的，我应该明确一下我是在问child.add是否是add函数的尾调用，而不是forEach回调函数。 - pixelmike

@pixelmike：只有相对于当前执行的函数，调用才能处于尾位置。调用堆栈中的其他函数或词法作用域中的函数并不重要。 - Bergi

Rauschmayer不同意（必须稍微向上滚动，顶部的横幅会遮挡目标）。您能指出规范在哪里定义了child.add(n)作为forEach回调的尾位置吗？ - T.J. Crowder

Answer 2

有任何Javascript引擎进行尾调用优化吗？

目前的JavaScript不会为此进行优化

另一个选择是使用trampoline https://taylodl.wordpress.com/2013/06/07/functional-javascript-tail-call-optimization-and-trampolines/

- exussum

---

是的，我并不认为优化已经完成了，但我正在尝试为它准备好。感谢提供链接。 - pixelmike

你链接的那个问题已经过时了。ES6现在拥有适当的尾调用优化。 - Bergi

假定它是正确的，截至今天，http://kangax.github.io/compat-table/es6/ 中没有任何东西使用它。 - exussum

@exussum：是的，这个草案还没有被接受，但所有功能已经逐渐在引擎中实现。正如您所看到的，一些转译器已经有了优化措施。 - Bergi

虽然我同意链接仍然有效，但早期采用可能会改变，但是没有尾部优化。可能会有语法更改以允许尾调用优化。这是未知的，除非您遵循草案，否则无法进行实现。 - exussum

ES5 绝对没有尾调用优化，但是 ES6 会有。这是规范的一部分 :) - TaoPR