1

我有一个关于这篇文章的问题。

这段代码之间

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无论如何？我也不清楚。

4

3 回答 3

1

我对这有多大帮助感到困惑。第二个片段是否只是有一个尾调用，它会产生更少的开销，因为它会在再次调用自己之前计算它需要什么，或者我还缺少什么？

据我了解，尾调用仍未消除，只是进行了优化。

如果一个过程的结束看起来像这样：

push args
call foo
return

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

jump startOfFoo

完全消除过程调用。

为什么还需要赔率和赔率1？我也不清楚。

的“契约”odds只指定了两个参数——第三个参数只是一个实现细节。因此，您将其隐藏在内部方法中，并将“包装器”呈现为外部 API。

我想你可以打电话给odds1类似的东西oddsImpl，这样会更清楚。

于 2011-01-16T20:44:09.893 回答
1

第一个版本不是尾递归的，因为在获得它的值之后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具有and的原因odds1只是为了在其他代码调用此函数时提供初始累加器值。

于 2011-01-16T20:51:17.370 回答
1

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

递归地，这也将发生在下一个调用中，以及之后的调用中，依此类推。因此，当我们到达递归结束并开始返回值并计算产品时，我们有 n 个待处理的操作。

在第二个例子中，由于执行的 return 语句很简单return odds1(n - 1, p - 1, (n / p) * acc)，我们可以计算函数参数，并简单地调用odds1(n-1)而不保留我们当前的位置。这就是优化的地方，因为现在我不必记住每次在堆栈上打开一个新框架时我在哪里。

把它想象成书籍参考。想象一下你打开一本食谱，去找一个食谱，配料表如下：

  1. 盐
  2. 下一页的成分

下一页有

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

等你怎么知道所有的成分是什么？您必须记住您在每一页上看到的内容！

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

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

下一页有：

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

等到您到达最后一页时（请注意，类比是准确的，因为两者都采用相同数量的函数调用），您拥有所有成分，而不必“记住”您在每一页上看到的内容，因为这一切都在最后一页！

于 2011-01-16T20:55:39.560 回答