scala - 用于理解时递归调用不在尾部位置

Question

我不知道是我做错了什么，还是只是 Scala 编译器的一个属性——当我尝试编译这段代码时，我得到了提到的编译错误:

@tailrec
def shiftDown2(x: Int, bound: Int) {
  val childOfX = chooseChild(x, bound)
  for (child <- childOfX) {
    swap(x, child)
    shiftDown2(child, bound)
  }
}

下面的代码编译没有问题:

@tailrec
def shiftDown(x: Int, bound: Int) {
  val childOfX = chooseChild(x, bound)
  if (childOfX.isDefined) {
    swap(x, childOfX.get)
    shiftDown(childOfX.get, bound)
  }
}

我相信上面的代码片段在语义上是相同的，并且都应该使用尾递归。

Answer 1

尾递归优化不适用于 for 循环内的递归调用，因为这里的 for 循环只是调用 foreach 的语法糖-订购方法。因此，您的代码等效于:

@tailrec
def shiftDown2(x: Int, bound: Int) {
  val childOfX = chooseChild(x, bound)
  childOfX.foreach { child =>
    swap(x, child)
    shiftDown2(child, bound)
  }
}

scalac 只有在递归方法直接尾调用自身时才能优化尾调用 - 通过将其转换为类似于字节码中的 while 循环。

不幸的是，这里不是这种情况 - shiftDown2 调用 childOfX.foreach 传递给它一个匿名函数。然后，foreach(可能)调用该匿名函数的apply，该匿名函数最终再次调用shiftDown2。所以这是一个间接递归，不能被scalac优化。此限制源于 JVM，它没有 native 尾调用支持。