可以函数tail-recursive

Question

我有一些递归代码我想重构使用Enumerator的尾递归,我可以简化这种递归看起来像这样,请忽略这个功能想要实现的功能.

@tailrec
def doStuff: List[Int] => Int = {
      case Nil => 0
      case x :: xs => doStuff(xs)
    }

如果我摆脱tailrec注释,它工作正常,结构看起来像这个doStuff(doStuff(doStuff(..))).它将具有stackoverflow异常.

那么如果它是一个函数,我怎么能使它递归递归

Answer 1

匿名函数不能进行尾递归.让我们首先对代码进行非常简单的重写,以引入一个val来保存结果函数.

@tailrec
def doStuff: List[Int] => Int = {
  val result: List[Int] => Int = {
    case Nil => 0
    case x :: xs => doStuff(xs)
  }
  result
}

从那里应该很清楚,那doStuff(xs)就是没有调用匿名函数本身.它正在调用方法doStuff,该方法返回您要调用的函数.更糟糕的是,因为它是a def,它实际上在每次调用时返回不同的函数.因此,匿名函数绝对不是自称.

问题归结为这个简单的事实:匿名函数是匿名的.因此,他们无法直接调用自己:他们总是在调用其他人def或val可能会自行返回,但编译器并不知道.

出于这个原因,只有def像@dhg提出的那样才能真正实现尾递归.

现在,如果你真的想要返回一个函数值,这恰好是用尾递归的情况实现的,你可以简单地将一个方法转换为一个函数theMethod _.因此,您的初始问题的解决方案如下:

val doStuff = {
  @tailrec
  def rec(list: List[Int]): Int = list match {
    case Nil => 0
    case x :: xs => rec(xs)
  }
  rec _
}

请注意,我们声明了一个正确的尾递归方法(rec),然后我们将其转换为函数值rec _.