Does Scala support tail recursion optimization?

Question

Does Scala support tail recursion optimization?

Answer 1

Scala does tail recursion optimisation at compile-time, as other posters have said. That is, a tail recursive function is transformed into a loop by the compiler (a method invoke is transformed into a jump), as can be seen from the stack trace when running a tail recursive function.

Try the following snippet:

def boom(n: Int): Nothing = if(n<=0) throw new Exception else boom(n-1)
boom(10)

and inspect the stack trace. It will show only one call to the function boom - therefore the compiled bytecode is not recursive.

There is a proposal floating around to implement tail calls at the JVM level - which in my opinion would a great thing to do, as then the JVM could do runtime optimizations, rather than just compile time optimizations of the code - and could possibly mean more flexible tail recursion. Basically a tailcall invoke would behave exactly like a normal method invoke but will drop the stack of the caller when it's safe to do so - the specification of the JVM states that stack frames must be preserved, so the JIT has to do some static code analysis to find out if the stack frames are never going to be used.

The current status of it is proto 80%. I don't think it will be done in time for Java 7 (invokedynamic has a greater priority, and the implementation is almost done) but Java 8 might see it implemented.

Answer 2

In Scala 2.8 you can use @tailrec to mark specific method that you expect the compiler will optimise:

import scala.annotation.tailrec

@tailrec def factorialAcc(acc: Int, n: Int): Int = {
  if (n <= 1) acc
  else factorialAcc(n * acc, n - 1)
}

If a method can not be optimized you get a compile-time error.

Answer 3

Scala 2.7.x supports tail-call optimization for self-recursion (a function calling itself) of final methods and local functions.

Scala 2.8 might come with library support for trampoline too, which is a technique to optimize mutually recursive functions.

A good deal of information about the state of Scala recursion can be found in Rich Dougherty's blog.

Answer 4

Only in very simple cases where the function is self-recursive.

Proof of tail recursion ability.

It looks like Scala 2.8 might be improving tail-recursion recognition, though.