Why won’t the Scala compiler apply tail call optimization unless a method is final?

by

Consider the following interaction with the REPL. First we define a class with a factorial method:

scala> class C {
         def fact(n: Int, result: Int): Int =
           if(n == 0) result
           else fact(n - 1, n * result)
       }
defined class C

scala> (new C).fact(5, 1)
res11: Int = 120

Now let’s override it in a subclass to double the superclass’s answer:

scala> class C2 extends C {
         override def fact(n: Int, result: Int): Int = 2 * super.fact(n, result)
       }
defined class C2

scala> (new C).fact(5, 1)
res12: Int = 120

scala> (new C2).fact(5, 1)

What result do you expect for this last call? You might be expecting 240. But no:

scala> (new C2).fact(5, 1)
res13: Int = 7680

That’s because when the superclass’s method makes a recursive call, the recursive call goes through the subclass.

If overriding worked such that 240 was the right answer, then it would be safe for tail-call optimization to be performed in the superclass here. But that isn’t how Scala (or Java) works.

Unless a method is marked final, it might not be calling itself when it makes a recursive call.

And that’s why @tailrec doesn’t work unless a method is final (or private).

UPDATE: I recommend reading the other two answers (John’s and Rex’s) as well.

More Related Contents:

  1. How do I break out of a loop in Scala?
  2. What is the Scala annotation to ensure a tail recursive function is optimized?
  3. How to bucket the range of values from a column and count how many values fall into each interval in scala?
  4. What does `:_*` (colon underscore star) do in Scala?
  5. How do I detect if a Spark DataFrame has a column
  6. Difference between object and class in Scala
  7. Type inference fails on Set made with .toSet?
  8. How to force DataFrame evaluation in Spark
  9. private[this] vs private
  10. call of distinct and map together throws NPE in spark library
  11. How to get path to the uploaded file
  12. Why is the Aux technique required for type-level computations?
  13. java.lang.NoSuchMethodError: scala.Predef$.refArrayOps
  14. Accessing the underlying ActorRef of an akka stream Source created by Source.actorRef
  15. Scala and forward references [duplicate]
  16. Error with varargs for function-objects in Scala?
  17. Abstract types versus type parameters
  18. How do I parse command line arguments in Scala? [closed]
  19. How to print the contents of RDD?
  20. Is there an equivalent to SuppressWarnings in Scala?
  21. Why isn’t Validation a Monad?
  22. Can I import from multiple packages all at once in Scala?
  23. How is this case class match pattern working?
  24. Futures / Success race
  25. Scala start Play server in production
  26. Scala-Spark Dynamically call groupby and agg with parameter values
  27. Joining two dataframes without a common column
  28. Why does one select Scala type members with a hash instead of a dot?
  29. Scala best way of turning a Collection into a Map-by-key?
  30. Is it possible to have tuple assignment to variables in Scala? [duplicate]

Leave a Comment