关于“尾声优化”文章的问题

Question

我有一个问题 这个 文章。

在此代码之间

function odds(n, p) {
  if(n == 0) {
    return 1
  } else {
    return (n / p) * odds(n - 1, p - 1)
  }
}

和此代码

(function(){
  var odds1 = function(n, p, acc) {
    if(n == 0) {
      return acc
    } else {
      return odds1(n - 1, p - 1, (n / p) * acc)
    }
  }

  odds = function(n, p) {
    return odds1(n, p, 1)
  }  
})()

1）我对这有多大的帮助感到困惑。第二个摘要是否只有一个尾巴呼叫会少产生开销，因为它可以在再次自称之前计算其所需的内容，还是我缺少更多的东西？

据我了解，尾声仍未消除，只是优化了。

2）为什么需要 odds 和 odds1 反正？我也不清楚。

Answer 1

我对这有多大的帮助感到困惑。第二个摘要是否只有一个尾巴呼叫会少产生开销，因为它可以在再次自称之前计算其所需的内容，还是我缺少更多的东西？

据我了解，尾声仍未消除，只是优化了。

如果过程的结尾看起来像这样：

push args
call foo
return

然后编译器可以将其优化为

jump startOfFoo

完全消除程序调用。

为什么无论如何都需要赔率和赔率1？我也不清楚。

的“合同” odds 仅指定两个参数 - 第三个参数只是实现细节。因此，您将其隐藏在内部方法中，并将“包装器”作为外部API。

你可以打电话 odds1 就像是 oddsImpl 我认为这将使它变得更加清晰。

Answer 2

第一个版本不是 尾部递归 因为在获得价值之后 odds(n - 1, p - 1) 然后必须将其乘以 (n / p), ，第二版将其移至计算参数的计算 odds1 功能使其适当地递归。

如果您查看呼叫堆栈，那么第一个会像这样：

odds(2, 3)
  odds(1, 2)
    odds(0, 1)
    return 1
  return 1/2 * 1
return 2/3 * 1/2

第二个是：

odds(2, 3)
  odds1(2, 3, 1)
    odds1(1, 2, 2/3)
      odds1(0, 1, 1/2 * 2/3)
      return 1/3
    return 1/3
  return 1/3
return 1/3

因为您只是返回递归调用的值，所以编译器可以轻松地优化它：

odds(2, 3)
#discard stackframe
odds1(2, 3, 1)
#discard stackframe
odds1(1, 2, 2/3)
#discard stackframe
odds1(0, 1, 1/3)
return 1/3

拥有的原因 odds 和 odds1 仅当其他代码调用此功能时，仅提供初始累加器值。

Answer 3

在第一个示例中，尾部递归的优化如下，因为您无法计算乘法的结果 return (n / p) * odds(n - 1, p - 1) 在您打电话给赔率（N-1）之前，插座器必须保持我们当前在内存中的位置（在堆栈上），并打开一个新的调用赔率。

递归地，这也将在下一个呼叫中以及之后的呼叫中发生。因此，到达递归结束时，我们进行了N待定操作，并开始返回值并计算产品的值。

在第二个示例中，由于执行的返回语句是简单的 return odds1(n - 1, p - 1, (n / p) * acc) 我们可以计算函数参数，只需调用赔率1（n-1） 没有持有我们目前的职位. 。这是优化的地方，因为现在我不必记住每次在堆栈上打开新框架时的位置。

将其视为书籍参考。想象一下，您打开一本食谱并转到特定食谱，并且成分如下：

1. 盐
2. 下一页上的成分

下一页有

1. 胡椒
2. 下一页上的成分

等等。您如何说明所有成分是什么？您必须记住您在每一页上看到的内容！

尽管第二个示例更像以下成分列表：

1. 盐
2. 忘记这一点，只需使用您在下一页上看到的内容

下一页有：

1. 盐
2. 胡椒
3. 忘记这一点，只需使用您在下一页上看到的内容

等等等。到您到达最后一页时（请注意，类比是准确的，因为两者都采用相同数量的函数调用），您就有所有成分，而无需“保留记忆”您在每个页面上看到的内容，因为这一切都在最后一页！