Use of recursion in Scala when run in the JVM

Question

From searching elsewhere on this site and the web, tail call optimization is not supported by the JVM. Does that therefore mean that tail recursive Scala code such as the following, which may run on very large input lists, should not be written if it is to run on the JVM?

// Get the nth element in a list    
def nth[T](n : Int, list : List[T]) : T = list match {
            case Nil => throw new IllegalArgumentException
            case _ if n == 0 => throw new IllegalArgumentException
            case _ :: tail if n == 1 => list.head
            case _ :: tail  => nth(n - 1, tail)
}

Martin Odersky's Scala by Example contains the following paragragh which seems to suggests that there are circumstances or other environments where recursion is appropriate:

In principle, tail calls can always re-use the stack frame of the calling function. However, some run-time environments (such as the Java VM) lack the primitives to make stack frame re-use for tail calls efficient. A production quality Scala implementation is therefore only required to re-use the stack frame of a di- rectly tail-recursive function whose last action is a call to itself. Other tail calls might be optimized also, but one should not rely on this across implementations.

Can anyone explain what this middle two sentences of this paragraph mean?

Thank you!

Answer 1

Since direct tail recursion is equivalent to a while loop, your example will run efficiently on the JVM because the Scala compiler can compile this to a loop under the hood, simply using a jump. General TCO however is not supported on the JVM, although there is available the tailcall() method which supports tail calls using compiler-generated trampolines.

To ensure that the compiler can correctly optimize a tail-recursive function to a loop, you can use the scala.annotation.tailrec annotation, which will cause a compiler error if the compiler cannot make the desired optimization:

import scala.annotation.tailrec

@tailrec def nth[T](n : Int, list : List[T]) : Option[T] = list match {
            case Nil => None
            case _ if n == 0 => None
            case _ :: tail if n == 1 => list.headOption
            case _ :: tail  => nth(n - 1, tail)
}

(screw IllegalArgmentException!)

Answer 2

In principle, tail calls can always re-use the stack frame of the calling function. However, some runtime environments (such as the Java VM) lack the primitives to make stack frame re-use for tail calls efficient. A production quality Scala implementation is therefore only required to re-use the stack frame of a di rectly tail-recursive function whose last action is a call to itself. Other tail calls might be optimized also, but one should not rely on this across implementations.

Can anyone explain what this middle two sentences of this paragraph mean?

Tail recursion is a special case of a tail call. Direct tail recursion is a special case of tail recursion. Only direct tail recursion is guaranteed to be optimized. Others may be optimized, too, but that's basically just a compiler optimization. As a language feature, Scala only guarantees direct tail recursion elimination.

So, what's the difference?

Well, a tail call is simply the last call in a subroutine:

def a = {
  b
  c
}

In this case, the call to c is a tail call, the call to b is not.

Tail recursion is when a tail call calls a subroutine that was already called before:

def a = {
  b
}

def b = {
  a
}

This is tail recursion: a calls b (a tail call), which in turn calls a again. (In contrast to the direct tail recursion described below, this is sometimes called indirect tail recursion.)

However, none of the two examples will get optimized by Scala. Or, more precisely: a Scala implementation is allowed to optimize them, but it is not required to do so. This is in contrast to, e.g. Scheme, where the language specification guarantees that all of the above cases will take O(1) stack space.

The Scala Language Specification only guarantees that direct tail recursion is optimized, i.e. when a subroutine directly calls itself with no other calls in between:

def a = {
  b
  a
}

In this case, the call to a is a tail call (because it is the last call in the subroutine), it is tail recursion (because it calls itself again) and most importantly it is direct tail recursion, because a directly calls itself without going through another call first.

Note that there are many subtle things that may lead to a method not being directly tail-recursive. For example, if a is overloaded, then the recursion may actually go through different overloads, and thus would no longer be direct.

In practice, this means two things:

1. you cannot perform an Extract Method Refactoring on a tail-recursive method, at least not including the tail call, because this would turn a directly tail-recursive method (which will get optimized) into an indirectly tail-recursive method (which will not get optimized).
2. You can only use direct tail recursion. A tail-recursive descent parser, or a state machine, which can be very elegantly expressed using indirect tail recursion, are out.

The main reason for this is that when your underlying execution engine lacks powerful control flow manipulation features such as GOTO, continuations, first-class mutable stack or proper tail calls, then you need to either implement your own stack on top of it, use trampolines, make a global CPS transform or something similarly nasty, in order to provide generalized proper tail calls. All of these have either severe impact on performance or interoperability with other code on the same platform.

Or, as Rich Hickey, the creator of Clojure, said when he was facing the same problem: "Performance, Java interop, tail calls. Pick two." Both Clojure and Scala chose to compromise on tail calls and provide only tail recursion and not full tail calls.

To cut a long story short: yes, the specific example you posted will be optimized, since it is direct tail recursion. You can test this by putting an @tailrec annotation on the method. The annotation does not change whether or not the method gets optimized, it does however guarantee that you will get a compile error if the method can not be optimized.

Due to the above-mentioned subtleties, it is generally a good idea to put an @tailrec annotation on methods that you need to be optimized, both in order to get a compile error, but also as a hint to other developers maintaining your code.

Answer 3

The Scala compiler will attempt to optimize tail calls by "flattening" them into a loop that won't cause a continually expanding stack.

Of course, your code has to be optimizable for it to do so. If you use the annotation @tailrec before your method however (scala.annotation.tailrec) the compiler will REQUIRE the method be optimizable or fail to compile.

Answer 4

Martin's remark is saying that only directly self-recursive calls are candidates (other criteria being met) for the TCO optimization. Indirect, mutually recursive method pairs (or larger sets of recursive methods) cannot be so optimized.