Search code examples
scalarecursionstack-overflowtail-recursion

Scala tail recursion optimization inside a match

I am teaching myself Scala by trying to implement the operations on List[T]. I just implemented dropWhile and it made me wonder about how tail recursion optimization works when the recursive call appears in different cases.

def dropWhile[T](list: List[T])(predicate: T => Boolean): List[T] = list match {
  case head :: tail if predicate(head) => dropWhile(tail)(predicate)
  case _ => list
}

Does it matter that the recursive call appears in the first case?

Solution

  • As some one said in the comments, you can apply the @tailrec annotations to your function and it will give a compiler error if the recursion can not be optimized to a loop.

    Where the recursive call is does not matter. The important part is that there is no need for a stack frame to stay allocated waiting for the return from the recursive calls.