Scala Tail Recursion Optimization on Short-Circuited Boolean Operations

Question

I wrote a function like this in Scala:

def isSorted[T](list : List[T])(compare : (T, T) => Boolean) : Boolean = {
    list match {
        case Nil => true
        case x :: Nil => true
        case x :: rest => !compare(rest.head, x) && isSorted(rest)(compare)
    }
}

I am curious whether the compiler will optimize away the recursive call. The recursive call can only happen if the leading comparison succeeds. If not, is there a way to bomb out early and still achieve tail recursion optimization?

Answer 1

So, as @omnomnom says, you can check whether something is being TCO-ed by adding the @tailrec annotation to the method. The compiler will throw an error if it's unable to optmise it.

We can verify this with a simple example:

@tailrec
def fact(n : Int) : Int = fact(n - 1) * 2

The compiler bombs out with the following error:

test.scala:6: error: could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

Trying this on your program, however, the answer is... yes! So apparently the compiler is happy to optimise your tail-call away :-)