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?
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..
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:
@tailrec just gives up)
According to this article from April 2014:
It's important to note that this isn't a bug in the JVM. It's an optimization that can be implemented to help functional programmers who use recursion, which is much more common and normal in those languages. I recently spoke to Brian Goetz at Oracle about this optimization, and he said that it's on a list of things to be added to the JVM, but it's just not a high-priority item.
Tail recursion of Factorial in java, it has space complexity of O(1)
int tailFactorial(int x){
return tailFactorial(x, 1);
}
int tailFactorial(int x, int totalFactor){
if(x == 0){
return totalFactor;
}else{
return tailFactorial(x-1, totalFactor * x);
}
}
