是不是在尾部recursion风格的代码？

我有点新的斯卡拉试图读大卫波拉克开始Scala。 他定义了一个简单的recursion函数来加载文件中的所有string：

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

这是优雅和令人敬畏的，除了它已经引发了一个StackOverflowexception，当我试图加载一个巨大的字典文件。

现在据我所知，Scala支持尾recursion，所以函数调用不可能溢出堆栈，可能编译器不能识别它？ 所以一些谷歌search后，我试着@tailrec注释来帮助编译器，但它说

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

我理解尾recursion错了吗？ 我如何解决这个问题？

Answer 1

如果最后一次调用是对方法本身的调用，Scala只能优化它。

那么，最后一个调用不是所有的allStrings ，它实际上是:: :（cons）方法。

使尾部recursion的一种方法是添加一个累加器参数，例如：

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

为了防止累加器泄漏到API中，可以将尾recursion方法定义为嵌套方法：

 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

它不是尾recursion（而且永远也不可能），因为最后的操作不是对allStrings的recursion调用，而是对::方法的调用。

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

 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) } 

在这种情况下，你也可以将累加器提升到allStrings一个参数，给它一个默认的Nil值，并且避免使用inner方法。 但是这并不总是可能的，如果您关心互操作性，那么就不能从Java代码中很好地调用。