stella stella - 3 months ago 10
Scala Question

Why isn't a function tail recursive?

I'm reading Programming in Scala by M. Odersky and he says that


Functions like approximate, which call themselves as their last
action, are called tail recursive.


So, I tried this:

object Main extends App {
implicit val mc = new MyClass(8)
val ti = new TestImplct
ti.test
}

class TestImplct {
def test(implicit mc : MyClass): Unit = {
println(mc.i)
mc.i -= 1
if(mc.i < 0){
throw new IllegalArgumentException
}
test
}
}

class MyClass(var i : Int)


IDEONE DEMO

But it generates the following stack trace

Exception in thread "main" java.lang.IllegalArgumentException
at TestImplct.test(Main.scala:13)
at TestImplct.test(Main.scala:15)
at TestImplct.test(Main.scala:15)
at TestImplct.test(Main.scala:15)
at TestImplct.test(Main.scala:15)
at TestImplct.test(Main.scala:15)
at TestImplct.test(Main.scala:15)
at TestImplct.test(Main.scala:15)
at TestImplct.test(Main.scala:15)


Which means that it generates a new stack frame for each recursive call. But the last action is to call to itself. What's wrong and how to make it tail-recursive?

Why doesn't compiler do tail-call optimization?

Answer

You can try marking the method with @tailrec annotation. If you do that, compilation will fail and will show you why compiler couldn't optimize this to be tail recursive:

Main.scala:12: error: could not optimize @tailrec annotated method test: it is neither private nor final so can be overridden

Indeed, if you make the method final, it works as expected.