Isn't that code in tail recursive style?

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

Solution 2:

It's not tail recursive (and can't ever be) because the final operation is not a recursive call to allStrings, it's a call to the :: method.

The safest way to resolve this is with a nested method that uses an accumulator:

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

In this particular case, you could also lift the accumulator to a parameter on allStrings, give it a default value of Nil, and avoid the need for an inner method. But that's not always possible, and it can't be called nicely from Java code if you're concerned about interop.