CODEWITHSUNDEEP
scalarecursion
Knut Arne Vedaa
Knut Arne Vedaa

Reputation: 15742

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

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?

Upvotes: 8

Views: 637

Answers (2)

retronym
retronym

Reputation: 55028

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 = {
                        ^

Upvotes: 10

Francois G
Francois G

Reputation: 11985

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.

Upvotes: 16

Related Questions