编译器在非尾部位置提到递归函数而上当了

Question

我试图通过构建(自定义)延续来对结构尾部进行递归操作,但编译器不会接受我的代码是尾递归的.一旦我尝试声明一个引用非尾部位置的递归函数的函数文字,即使我没有在这里调用函数,它也会抛出错误.以下是触发错误的一个非常简单的虚拟示例:

import scala.annotation.tailrec
object Test extends App {
  @tailrec
  def tailrectest(i: Int): Int = i match {
    case i if i > 0 => {
      val x = () => tailrectest(10)
      tailrectest(i - 1)
    }
    case 0 => 0
  }
}

我明白了

could not optimize @tailrec annotated method tailrectest: it contains a recursive call not in tail position

它指的是行 val x = () => tailrectest(10)

Answer 1

我认为这个问题是由于当你将一个(递归)调用嵌入到函数变量中时x,编译器无法推断它是否会被调用(在这种简单的情况下,它是可能的).所以为了安全起见,它会抱怨它在函数体中发生的任何递归调用.

将递归调用放入变量后,变量可以从函数中转义(例如由函数返回,或存储在某个全局状态等).因此,它不能再作为尾递归循环进行优化.

也许发布您想要使用的方式,x以便我们可以尝试找到特定的解决方案.

Answer 2

我完全同意PetrPudlák的回答.但是对于它的价值,有一条出路:定义一个辅助方法来返回一个包装函数到tailrectest:

import scala.annotation.tailrec
object Test extends App {
  def tailrectest_ = tailrectest _
  @tailrec
  def tailrectest(i: Int): Int = i match {
    case i if i > 0 => {
      val x = () => tailrectest_(10)
      tailrectest(i - 1)
    }
    case 0 => 0
  }
}

这会给代码增加一些噪音,但至少它会起作用.

但是,如果您要做的是构建某种延续,那么您的真实代码肯定必须在闭包中捕获一些本地上下文,这就排除了我的上述解决方案.在这种情况下,我看不出一个简单的出路.

更新(2013年3月11日):

Petr Pudlak found a similar but superior solution in another question: http://stackoverflow.com/questions/15334611/how-to-make-a-tail-recusive-method-that-can-also-refer-to-itself-in-a-non-tail-r

By using an inner function, we can actually capture local state, which make it fully usable. Here is his solution, applied to entropyslave's original question:

import scala.annotation.tailrec

object Test extends App {
  def tailrectest(i: Int): Int = {
    @tailrec
    def tailrectestImpl(i: Int): Int = {
      i match {
        case i if i > 0 =>
          val x = () => tailrectest(10)
          tailrectestImpl(i - 1)
        case 0 => 0
      }
    }
    tailrectest( i )
  }
}