尾递归优化：为什么“+”不允许？

Question

所以我看到的尾递归的常见例子之一是：

function factorial(x) {
    if (x <= 0) {
        return 1;
    } else {
        return x * factorial(x-1); // (A)
    }
}

它针对尾调用进行了优化：

function factorial(n) {
    return facRec(n, 1);
}
function facRec(x, acc) {
    if (x <= 1) {
        return acc;
    } else {
        return facRec(x-1, x*acc); // (A)
    }
}

我明白了。但我的问题是：为什么*在这种情况下不是可以优化的功能？我不能将顶部重写为

function factorial(x) {
    if (x <= 0) {
        return 1;
    } else {
        return multiply(x, factorial(x-1)); // (A)
    }
}

我知道这行不通。我认为这只是因为它不是真正的尾递归调用？不过，这仍然是尾部优化吗？

Answer 1

您的最后一个示例不是尾调用，因为您必须factorial 在调用multiply. 考虑：

阶乘(5)
  在得到 factorial(4) 的结果之前不能调用乘法
    在得到 factorial(3) 的结果之前不能调用乘法
      在得到 factorial(2) 的结果之前不能调用乘法
        在得到 factorial(1) 的结果之前不能调用乘法
          在得到 factorial(0) 的结果之前不能调用乘法

只有在这一点上，您才停止递归并调用multiply. 所以，没有尾声。

可能还值得注意的是，TCO 几乎仅由 Safari 的 JavaScriptCore 实现。它不是由 Chrome 的 V8 或 Firefox 的 SpiderMonkey 实现的，也不太可能是规范或没有规范。:-) 更多这里和这里。

我应该注意到，在你的标题中你问

为什么“+”不允许？

确实如此。TCO 并不关心操作是什么 -*与+ - 只是它处于尾部位置。