用于理解时递归调用不在尾部位置 [英] Recursive call not in tail position when using for comprehensions

问题描述

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

I don't know if I am doing something wrong or it is just a property of the Scala compiler - I get the mentioned compilation error when I try to compile this code:

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

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

whilst the following code compiles without problems:

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

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

I believe that above code fragments are semantically the same and both should work with tail recursion.

推荐答案

尾递归优化不适用于 for 循环内的递归调用，因为这里的 for 循环只是用于调用 foreach 高阶方法的语法糖.所以，你的代码相当于:

Tail recursion optimization will not work with recursive invocations inside for loop, because for loop here is just a syntactic sugar for calling foreach higher-order method. So, your code is equivalent to:

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

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

scalac can optimize tail calls only if recursive method is tail-calling itself directly - by translating it into something similar to while loop in bytecode.

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

Unfortunately, this is not the case here - shiftDown2 calls childOfX.foreach passing it an anonymous function. Then, foreach (potentially) calls apply on that anonymous function and that anonymous function finally calls shiftDown2 again. So this is an indirect recursion and cannot be optimized by scalac. This limitation has its roots in the JVM, which doesn't have native tail call support.

这篇关于用于理解时递归调用不在尾部位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！