是不是在尾递归风格的代码？ [英] Isn't that code in tail recursive style?

问题描述

我对斯卡拉来说是一个新手，在阅读大卫波拉克的成长斯卡拉时尝试了一下。
他定义了一个简单的递归函数，用于加载文件中的所有字符串：

  def allStrings（expr：=>字符串）：List [String] = expr match {
 case null =>无
案例w => w :: allStrings（expr）
} 
  

一个StackOverflow异常，当我试图加载一个巨大的字典文件。

现在据我所知，Scala支持尾递归，所以函数调用不可能溢出堆栈，可能编译器不承认它？因此，在一些Google搜索之后，我尝试了@tailrec注释来帮助编译器出来，但它说：

 错误：无法优化@tailrec注释方法：它包含一个不在尾部位置的递归调用
 def allStrings（expr：=> String）：List [String] = 
  

我理解尾递归是否错误？我该如何解决这个问题？

解决方案

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

好的，最后一次调用不是 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）
} 
  

I'm kinda new to Scala trying it out while reading Beggining Scala by David Pollack. He defines a simple recursive function that loads all strings from the file:

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

It's elegant and awesome except that it had thrown a StackOverflow exception when I tried to load a huge dictionary file.

Now as far as I understand Scala supports tail recursion, so that function call couldn't possibly overflow the stack, probably compiler doesn't recognize it? So after some googling I tried @tailrec annotation to help the compiler out, but it said

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

Am I understanding tail recursion wrong? How do I fix this code?

解决方案

Scala can only optimise this if the last call is a call to the method itself.

Well, the last call is not to allStrings, it's actually to the :: (cons) method.

A way to make this tail recursive is to add an accumulator parameter, for example:

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

To prevent the accumulator leaking into the API, you can define the tail recursive method as a nested method:

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

这篇关于是不是在尾递归风格的代码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！