CODEWITHSUNDEEP
scalarecursiontail-recursion
stella
stella

Reputation: 2596

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?

Upvotes: 4

Views: 148

Answers (2)

Tzach Zohar
Tzach Zohar

Reputation: 37852

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.

Upvotes: 9

codejitsu
codejitsu

Reputation: 3182

Your code works correctly. Your value in the mc object decrease with every step. At the last step you get the exception.

You can change the return type of your function to be Boolean for example and return false when your value is < 0 otherwise you return true.

I would suggest, you use '@tailrec' annotation in order to get checked the recursive function call by compiler.

Upvotes: 2

Related Questions