时间戳

首页 > 解决方案 > 尾递归优化：为什么 '+' 不允许这样做？

javascript - 尾递归优化：为什么 '+' 不允许这样做？

问题描述

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

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

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

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)
    }
}

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

标签： javascriptrecursiontail-recursion

解决方案

您的最后一个示例不是尾随呼叫，因为您必须先继续呼叫factorial ，然后才能呼叫multiply。考虑：

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

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

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

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

为什么'+'不允许这样做？

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

推荐阅读