可以进行尾递归

Question

我有一些递归代码，我想重构以使用枚举器的尾递归，我可以将该递归简化为如下所示，请忽略此功能想要实现的功能。

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

如果我摆脱了 tailrec 注释，它工作正常，结构看起来像这个 doStuff(doStuff(doStuff(..(((。它将具有堆栈溢出异常。

那么如果它是一个函数，我怎样才能让它成为尾递归的

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 ，返回要调用的函数。更糟糕的是，由于它是一个def，它实际上在每次调用时都返回一个不同的函数。因此，匿名函数绝对不会调用自身。

这个问题概括为这个简单的事实：匿名函数是匿名的。因此，他们无法直接调用自己：它们总是调用可能返回自己的其他def或val，但编译器不知道这一点。

出于这个原因，只有像@dhg提出的适当的def才会真正是尾递归的。

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

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

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

Answer 2

可能你的意思是这个？

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

Answer 3

那么如果它是一个函数，我怎样才能让它成为尾递归的

你不能。我的意思是，当然你可以在 Scala 中编写一个尾递归函数，但它不会帮助你，因为它不会得到优化。

Scala 只优化直接尾递归方法调用。