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 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)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);
}
}