关于"Tail Call Optimization“文章的问题

Question

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

在此代码之间

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

完全消除了过程调用。

，为什么要有odds和odds1呢？对我来说也不是很清楚。

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

我想，你可以像oddsImpl那样调用odds1，这样会更清楚。

Answer 2

第一个版本不是tail recursive，因为在获得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

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

递归地，这也将发生在下一次调用中，以及下一次调用中，以此类推。因此，当我们到达递归的末尾，开始返回值并计算乘积时，我们有n个未决的操作。

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

把它想象成书本参考资料。想象一下，你打开一本食谱，进入某个食谱，食材如下：

下一页上的

1. salt
2. the配料

下一页有

下一页上的

1. pepper
2. the配料

等等，你怎么知道所有的成分都是什么？你必须记住你在每一页上看到的东西！

虽然第二个例子更像是下面的配料表：

1. salt
2. forget这个，就用你在下一页看到的

下一页包含：

1. salt
2. pepper
3. forget这个，就用你在下一页看到的

当你到达最后一页时(请注意，类比是准确的，因为两者都需要相同数量的函数调用)，你已经拥有了所有的成分，而不必“记住”你在每一页上看到的内容，因为它们都在最后一页！