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

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,它没有本机尾调用支持.