是不是在尾部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错了吗? 我如何解决这个问题?

如果最后一次调用是对方法本身的调用,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) } 

它不是尾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代码中很好地调用。