Why isn't a function tail recursive?

Question

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?

I see you have defined the class. But I dont see where you instantiated it. — Samar
@Samar Ah, you're right. i didn;t attach the full code. My appologies. — stella
Its working fine. Why do you think its not tail recursive? Its just exiting because of the if condition. — Samar

Tzach Zohar Tzach Zohar · Accepted Answer · 2016-08-30T09:41:48

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.

Why isn't a function tail recursive?

2 Answers