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

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

你的最后一个例子不是尾调用，因为你必须在可以调用 multiply 之前继续调用 factorial 。考虑：

factorial(5) can't call multiply until it has the result from factorial(4) can't call multiply until it has the result from factorial(3) can't call multiply until it has the result from factorial(2) can't call multiply until it has the result from factorial(1) can't call multiply until it has the result from factorial(0)

只是在此时停止递归并调用 multiply。所以，没有尾声。

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

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

Why does '+' not allow that?

确实如此。 TCO 不关心操作是什么——* vs +——只关心它在尾部位置。

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

Tail Recursion Optimization: Why does '+' not allow that?

javascript

recursion

tail-recursion