Does Scala support tail recursion optimization?
Add a comment |
4 Answers
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.
3 Comments
J D
"The current status of it is proto 80%". I don't understand. I thought Arnold Schwaighofer completely implemented this under John Rose's guidance years ago?
Cubic
@JanHarrop maybe that was about tail recursion rather than general tail calls?
J D
@Cubic: No, it was general tail calls. Arnold also implemented them in LLVM.
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.
1 Comment
Callum
It is necessary to import the annotation with "import scala.annotation.tailrec"
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.
1 Comment
Vadzim
Also about monadic trampolines: apocalisp.wordpress.com/2011/10/26/…
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.
1 Comment
Giorgio
"Only in very simple cases where the function is self-recursive.": Does this mean that when using continuations one could easily run out of stack space?