4

我试图通过构建（自定义）延续来对结构尾递归进行操作，但编译器不会接受我的代码是尾递归的。一旦我尝试声明一个在非尾位置引用递归函数的函数文字，即使我没有在这里调用该函数，它也会引发错误。以下是触发错误的一个经过大量提炼的虚拟示例：

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)

4

2 回答 2

8

我相信问题是由于当您将（递归）调用嵌入函数变量x时，编译器通常无法推断它是否会被调用（在这种简单的情况下，这是可能的）。所以为了安全起见，它会抱怨它在函数体中发生的任何递归调用。

一旦对变量进行递归调用，该变量就可以从函数中逃逸（例如被函数返回，或者存储在某个全局状态中等），因此不能再将其优化为尾递归循环。

也许发布您想如何使用x，以便我们可以尝试找到特定的解决方案。

于 2012-09-10T17:35:02.917 回答
5

我完全同意 Petr Pudlá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 )
  }
}
于 2012-09-10T19:17:37.097 回答