Tail recursion: comparing two cases

Question

Why is this tail recursion:

  def navigate(myList : List[Int]) : (Int, List[Int]) = {
    def navigate(step: Int, offset: Int, myList: List[Int]): (Int, scala.List[Int]) = {
      if //some test and exit condition, then a definition of jump
      else navigate(step + 1, offset + jump, myList)
    }
    navigate(0, 0, myList)
  }

while this is not:

def navigate(myList : List[Int]) : (Int, List[Int]) = {
  navigate(0, 0, myList)
}

def navigate(step: Int, offset: Int, myList: List[Int]): (Int, scala.List[Int]) = {
  if //some test and exit condition, then a definition of jump
  else navigate(step + 1, offset + jump, myList)
}

If myList is very long, the first case does not give any problem, when the second one causes a StackOverflowError.

Also, is there any way to say the compiler that the latter should be compiled so that the recursion does not increase the stack?

https://anadea.info/blog/tail-recursion-in-scala might be of some use, what I got out of that is you can annotate with `@tailrec` and you'll get a compiler warning if it's not optimized. — ameer, Dec 05 '17 at 21:11
Also this https://stackoverflow.com/questions/3114142/what-is-the-scala-annotation-to-ensure-a-tail-recursive-function-is-optimized seems like you would get a somewhat detailed notice about why it's not optimized. — ameer, Dec 05 '17 at 21:13
@ameer I tried already but I got the compilation error "Method annotated with '@tailrec' is nither private nor final (so can be overridden)" which in my case can be good, but in general may not... — marco, Dec 05 '17 at 21:17
I'm guessing the fact that the method in the first example is private/final due to the scope (being embedded in the outer navigate means it won't be modified). Did you try making the second example navigate private/final? — ameer, Dec 05 '17 at 21:42
Yes, I made it private, and it works. But still don't understand what is the meaning of this. — marco, Dec 05 '17 at 21:54
Making it private/final means that it can't be overridden as the warning says (e.g. the function definition can't change later after it's been defined once). If that was not the case then the optimization would be invalid as the definition of the function that is being recursed could change, so we couldn't be sure it was safe to make the change from a recursive function call to a loop and the function call would need to remain in place. — ameer, Dec 05 '17 at 22:03
thank you ameer, for your help. To be honest I still don't deeply understand the reason, it would be useful an example or a reading about this. I'll google it. — marco, Dec 05 '17 at 23:01

score 4 · Answer 1 · answered Dec 05 '17 at 23:18

In order for a method to be eligible for tail-recursion optimization, it must:

be tail-recursive (duh!)
not use return
be final

Both of your examples conform to #1 and #2, but only the first example conforms to #3 (local methods are implicitly final).

The reason why a method is not tail-recursive if it is not final is that "tail-recursive" means "tail-calls itself", but if the method is virtual, then you cannot know whether it tail-calls itself or an overridden version of itself. Figuring out at compile time whether a method has been overridden requires Class Hierarchy Analysis, which is known to be equivalent to solving the Halting Problem … IOW is impossible.

Also, is there any way to say the compiler that the latter should be compiled so that the recursion does not increase the stack?

No. There is no way to turn tail-recursion optimization on or off. Methods that are tail-recursive (according to the Scala Language Specification's definition of "tail-recursive", of course) are always optimized. Any implementation of Scala that does not do this is in violation of the Scala Language Specification.

There is, however, the scala.annotation.tailrec annotation, which guarantees that the compiler will generate an error if a method that is annotated with this annotation does not comply with the SLS's definition of tail-recursion.

thanks! "you cannot know whether it tail-calls itself or an overridden version of itself" thanks, this is exactly what I missed. — marco, Dec 06 '17 at 14:12

Tail recursion: comparing two cases

1 Answers1