Isn't that code in tail recursive style?

Question

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?

Answer 1

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