尾递归风格的代码不是吗？

Question

我对Scala的新手在尝试阅读David Pollack的Beggining Scala时有点新意.他定义了一个简单的递归函数,它从文件中加载所有字符串:

def allStrings(expr: => String): List[String] = expr match {
    case null => Nil
    case w => w :: allStrings(expr)
}

它优雅而且很棒,只是当我试图加载一个庞大的字典文件时它抛出了一个StackOverflow异常.

现在据我所知,Scala支持尾递归,因此函数调用不可能溢出堆栈,可能编译器无法识别它？所以经过一些谷歌搜索后我尝试了@tailrec注释来帮助编译器,但它说

error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position
def allStrings(expr: => String): List[String] =

我理解尾递归错了吗？我该如何修复此代码？

Answer 1

如果最后一次调用是对方法本身的调用,Scala只能对此进行优化.

好吧,最后一次调用不是allStrings,它实际上是::(cons)方法.

使尾部递归的一种方法是添加累加器参数,例如:

def allStrings(expr: => String, acc: List[String] = Nil): List[String] =
  expr match {
    case null => acc
    case w => allStrings(expr, w :: acc)
  }

要防止累加器泄漏到API中,可以将尾递归方法定义为嵌套方法:

def allStrings(expr: => String) = {
  def iter(expr: => String, acc: List[String]): List[String] =
    expr match {
      case null => acc
      case w => iter(expr, w :: acc)
    }
  iter(expr, Nil)
}

Answer 2

它不是尾递归(并且不可能)因为最终操作不是递归调用allStrings,而是对::方法的调用.

解决这个问题最安全的方法是使用一个使用累加器的嵌套方法:

def allStrings(expr: => String) = {
  @tailrec
  def inner(expr: => String, acc: List[String]): List[String] = expr match {
    case null => acc
    case w => inner(expr, w :: acc)
  }
  inner(expr, Nil)
}

在这种特殊情况下,您还可以将累加器提升到参数on allStrings,给它一个默认值Nil,并避免使用内部方法.但这并不总是可行的,如果你担心互操作,它就不能从Java代码中很好地调用.