Method is tail recursive when defined on object but not on class

Question

Defining a recursive method on an object:

object Recursive {
    def recurse(maxDepth: Int = 10): Unit = {
        if (maxDepth == 0) throw new Exception
        recurse(maxDepth - 1)
    }
}

gives:

scala> Recursive.recurse(10)
java.lang.Exception
        at Recursive$.recurse(<console>:7)
        at .<init>(<console>:7)
        at .<clinit>(<console>)
        at RequestResult$.<init>(<console>:9)
        at RequestResult$.<clinit>(<console>)
        at RequestResult$scala_repl_result(<console>)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
        at java.lang.reflect.Method.invoke(Method.java:597)
        at scala.tools.nsc.Interpreter$Request$$anonfun$loadAndRun$1$$anonfun$apply$17.apply(Interpreter.scala:988)
        at scala.tools.nsc.Interpreter$Request$$anonfun$loadAndRun$1$$anonfun$apply$17.apply(Interpreter.scala:988)
        at scala.util.control.Exception$Catch.apply(Exception.scal...

But defining it on a class:

class Recursive {
    def recurse(maxDepth: Int = 10): Unit = {
        if (maxDepth == 0) throw new Exception
        recurse(maxDepth - 1)
    }
}

gives:

scala> new Recursive recurse(10)
java.lang.Exception
        at Recursive.recurse(<console>:7)
        at Recursive.recurse(<console>:8)
        at Recursive.recurse(<console>:8)
        at Recursive.recurse(<console>:8)
        at Recursive.recurse(<console>:8)
        at Recursive.recurse(<console>:8)
        at Recursive.recurse(<console>:8)
        at Recursive.recurse(<console>:8)
        at Recursive.recurse(<console>:8)
        at Recursive.recurse(<console>:8)
        at Recursive.recurse(<console>:8)
        at .<init>(<console>:7)
        at .<clinit>(<console>)
        at RequestResult$.<init>(<console>:9)
        at RequestResult$.<clinit>(<console>)
        at RequestResult$scala_repl_result(<console>)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAcc..

The methods are identical. Why is it not tail recursive when defined on a class?

Answer 1

If you want tail-recursion to be performed, recurse can not be overridable. If recurse is overridable, as in your class declaration, any recursion within it has to use dynamic method invocation (because it is potentially polymorphic), which can not be optimized to a goto-style statement.

The object singleton declaration statically ensures the unambiguous call to recurse, and lets the compiler proceed with tail recursion optimization.

Answer 2

If you expect a method to be tail recursive, you should annotate it with @tailrec. If the compiler can't apply TCO, it will error.

scala> import annotation._                           
import annotation._

scala> class Recursive {                                     
     |     @tailrec def recurse(maxDepth: Int = 10): Unit = {
     |         if (maxDepth == 0) throw new Exception        
     |         recurse(maxDepth - 1)                         
     |     }                                                 
     | }
<console>:12: error: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden
           @tailrec def recurse(maxDepth: Int = 10): Unit = {
                        ^