Search code examples
scalastack-overflowtail-recursiontail-call-optimization

Tail recursion issue

We were experimenting with parallel collections in Scala and wanted to check whether the result was ordered. For that, I wrote a small function on the REPL to do that check on the very large List we were producing:

def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => x>y & isOrdered(tail) 
  }
}

It fails with a stackOverflow (how appropriate for a question here!). I was expecting it to be tail-optimized. What's wrong?

Solution

  • isOrdered is not the last call in your code, the & operator is. Try this instead:

    @scala.annotation.tailrec def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => if (x>y) isOrdered(tail) else false
  }
}