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?

that's what [`@annotation.tailrec`](http://stackoverflow.com/questions/3114142/what-is-the-scala-annotation-to-ensure-a-tail-recursive-function-is-optimized) is for — om-nom-nom, Mar 19 '13 at 15:20
Just to be clear, `@tailrec` does not magically make the method tail-recursive, it makes it an error for it not to be tail-recursive. — Randall Schulz, Mar 19 '13 at 15:54

score 3 · Accepted Answer · answered Mar 19 '13 at 15:25

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

Interesting definition of `fact` you have there :) – Mysterious Dan Mar 19 '13 at 19:35 — Mysterious Dan, Mar 19 '13 at 19:35

Scala Tail Recursion Optimization on Short-Circuited Boolean Operations

1 Answers1