Does java support and optimize away tail-recursive calls?

Question

Say I got a recursive function that is tail recursive. I wonder if this function will be implemented as recursion, growing on the stack, or will it be changed to a loop (since it is a tail-recursive function)?

I have just read that Scala detects such calls and optimizes it but is this a Scala-only thing or JVM in general?

Answer 1

Java supports tail-recursive calls, but AFAIK it doesn't optimize them away. I think it's the Scala compiler that is simply capable of this, not the JVM itself. Check out the @tailrec annotation in Scala to see what more the compiler is capable of :)

But regardless of whether Java/JVM optimizes tail-recursion away, your function would be harder to optimize than necessary.

Look at this:

int sum(List<Integer> integers) {     return sum(integers, 0); }  int sum(List<Integer> integers, int sumSoFar) {     if (integers.isEmpty())         return sumSoFar;     else         return sum(                 integers.subList(1, integers.size()),                 sumSoFar + integers.get(0)         ); } 

See, I've added an overloaded sum with a so-far calculated sum parameter. This way when you recur in the else branch you don't need the actual stack frame any more - you got all you need as function arguments in the recursive call.

In your snippet the stack frame would probably have to exist as long as the recursive call..

Answer 2

Java and the JVM do not currently support tail calls

The fundamental work that needs to happen is at the level of the JVM, not Java. There has been a slow moving line of work to address this (initially as part of MLVM now under Project Loom). Despite being relatively old, this 2007 blog from John Rose is a good and short overview of how the JVM bytecode could be altered. I think that the tail call work was pushed aside in favor of finishing invokedynamic first (and that has uncovered more tricky design considerations for tail calls). Here is an excerpt from the latest Project Loom proposal:

As adding the ability to manipulate call stacks to the JVM will undoubtedly be required, it is also the goal of this project to add an even lighter-weight construct that will allow unwinding the stack to some point and then invoke a method with given arguments (basically, a generalization of efficient tail-calls). We will call that feature unwind-and-invoke, or UAI.

---

Some other details:

• Java as a language is unlikely to ever automatically optimize tail-calls. This is because most implementations of tail-call elimination have somewhat unintuitive effects on the callstack (eg. if you throw an exception in a recursive call, you won't see all of the recursive calls in the stack trace).

  JavaScript is an example of a language that tried to automatically optimize tail-calls (in ES2015), and here is a debrief from the V8 team explaining the difficulties. They've since removed the feature and have switched to backing a proposal that supports tail-call optimization only when it is explicit.

  If the JVM ever adds support for tail-calls at the bytecode level, I speculate Java might also support explicit tail-call optimization (ie. in the form of an annotation on a return or an annotation on a function or maybe even a new keyword).

• Scala tries to detect and optimize tail recursion into JVM bytecode loops. Here is a project that promises to perform this sort of optimization on existing JVM bytecode. The idea has not been adopted by Java because it is somewhat brittle and limited:

  1. mutually recursive functions get really tricky (Scala's @tailrec just gives up)
  2. polymorphic recursion can't work
  3. generalized tail calls obviously can't work