2

我不知道我做错了什么，或者它只是 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)
  }
}

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

4

1 回答 1

6

尾递归优化不适用于循环内的递归调用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，它不支持本机尾调用。

于 2013-10-05T16:50:21.383 回答