1. What is Scala?
As a multi-paradigm programming language, Scala combines the characteristics of object-oriented and functional programming. In Scala, tail recursion is used to prevent stack overflow problems through compiler optimization. Tail recursive optimization is a special optimization method that allows recursive calls to not use new stack frames, thereby avoiding stack overflow problems that occur when recursive calls are too deep.
2. What is tail recursion?
- Tail Recursion refers to theThe last stepIt is a recursive call that calls itself. In other words, after the recursive call is finished, there is no other operation, and the function can directly return the result.
- Since recursive calls are the last step, the result can be returned directly after the recursive call is completed, and the Scala compiler can convert this recursive into iteration, thus avoiding the use of additional stack space.
Features of tail recursion:
- Recursive calls are in functionsThe last operation。
- No additional calculations or operations occur after a recursive call.
Three. Tail recursive optimization implementation:
If we use recursive ideas to simply implement sums of 1 - 100000, we will write them as follows:
public class Main {
public static int sum(int n){
if(n == 1){
return 1;
}
return sum(n - 1) + n;
}
public static void main(String[] args) {
(sum(100000));
}
}But every recursive call will allocate space on the stack to save the local variables and return addresses of the current function. When the depth of recursion is too large, the space of the stack will be exhausted, resulting in*ErrorException (i.e. stack overflow error). This problem is related to the finite size of the stack. In the case of sum(100000), each recursive call needs to allocate space on the stack, which ultimately leads to stack overflow. So we use Scala to achieve tail recursive optimization.
When using Scala, tail recursion can be optimized into an iterative form by the compiler to avoid the bulging stack problem. The core of tail recursion is that recursive calls are the last step of the function. Java does not have built-in tail recursive optimization, so it needs to manually change the recursive to iterative form.
What is recursive calling the last step of a function?
def factorial(n: Int): Int = {
if (n == 1) {
1
} else {
n * factorial(n - 1) // Recursive call is not the last step, there are multiplication operations }
}- Here,
n * factorial(n - 1)Not tail recursion, because recursive callsfactorial(n - 1)There will be multiplication operations latern *。 - In this case, the recursive call will continuously create new stack frames, with the stack depth equal to
n, recursion is too deep and will cause stack overflow.
To optimize tail-recursion, we introduce an accumulator to store the calculation results:
import
@tailrec
def factorialTailRec(n: Int, accumulator: Int = 1): Int = {
if (n == 1) {
accumulator
} else {
factorialTailRec(n - 1, n * accumulator) // Recursive call is the last step, no other operation }
}- Here
factorialTailRec(n - 1, n * accumulator)It is a tail recursive call, because the recursive call is the last step in the function and directly returns the result. - use
@tailrecAnnotation lets the compiler ensure that the function meets the requirements of tail recursion.
Running process:
AssumptionfactorialTailRec(5, 1)The execution steps are:
-
factorialTailRec(5, 1)-> CallfactorialTailRec(4, 5) -
factorialTailRec(4, 5)-> CallfactorialTailRec(3, 20) -
factorialTailRec(3, 20)-> CallfactorialTailRec(2, 60) -
factorialTailRec(2, 60)-> CallfactorialTailRec(1, 120) -
factorialTailRec(1, 120)-> Return120。
The entire recursion process does not generate new stack frames, so it can prevent stack overflow.
So in the end we need to calculate the sum of 1-100000 and use tail recursive optimization to write it as follows:
import
object Main {
def main(args: Array[String]): Unit = {
println(sum(100000,0))
}
@tailrec //Check whether it is a tail recursion writing method (return returns only a function) def sum(n: Long, accumulator: Long): Long = {
if(n == 1){
return 1 + accumulator
}
return sum(n - 1,n + accumulator)
}
}4. Why do you have to use Scala?
Those who read this will definitely have a problem.Why do you have to use Scala to achieve tail recursive optimization? Is it impossible to use simple Java code to add tail recursive optimization?
In theory,Tail recursive optimizationIt is not a language-specific concept, and any language can be optimized with tail recursion.ScalaThe reason why tail recursive optimization is particularly emphasized is mainly because Scala's original intention is to support functional programming, and recursion is a commonly used construct in functional programming. Therefore, Scala provides a special optimization mechanism to prevent stack overflow problems caused by recursion.
By comparison,JavaThere is no built-in tail recursive optimization mechanism. Although Java can also write code with recursion at the end,Java Virtual Machine (JVM)Tail recursion is not automatically optimized. This limitation makes it possible to directly use tail recursion in JavaStack OverflowProblem, even if you follow the tail recursion writing method, it will not help.And Scala passes@tailrecAnnotations provide compiler support to ensure recursive tail optimization。
5. How to use Scala tail recursively optimized functions in Javaweb projects?
The implementation steps are divided into three steps:
- Configure Java projects to support Scala dependencies.
- Write Scala code, use tail recursion to implement the function, and add
@tailrecAnnotation. - Write Java code and call compiled Scala objects and methods.
1. First introduce the Maven configuration:
existAdd Scala support to the file:
<dependencies>
<!-- Scala runtime -->
<dependency>
<groupId>-lang</groupId>
<artifactId>scala-library</artifactId>
<version>2.13.8</version>
</dependency>
</dependencies>
<build>
<plugins>
<!-- Scala Maven Plugin -->
<plugin>
<groupId>net.</groupId>
<artifactId>scala-maven-plugin</artifactId>
<version>4.5.6</version>
<executions>
<execution>
<goals>
<goal>compile</goal>
<goal>testCompile</goal>
</goals>
</execution>
</executions>
</plugin>
</plugins>
</build>2. Write functions:
existsrc/main/scalaCreate a Scala file in the directory (for example,), define a tail recursive optimization function:
import
object TailRecSum {
// Accumulation function using tail recursive optimization @tailrec
def sum(n: Int, accumulator: Int): Int = {
if (n == 0) {
accumulator
} else {
sum(n - 1, accumulator + n)
}
}
}HeresumThe function is a tail recursive function, and the Scala compiler is adding@tailrecThe recursive function will be optimized after the annotation to prevent stack overflow.
3. Call the TailRecSum function in Java:
Write Java code and call Scala to compile and generate.classin the fileTailRecSumObject and itssummethod.
existsrc/main/javaWrite Java code in:
public class Main {
public static void main(String[] args) {
// Call the tail recursive optimization function in Scala int result = (100000, 0);
("Result: " + result);
}
}In this way, we can use Scala's powerful tail recursive optimization function in Java projects to avoid stack overflow problems caused by recursion.
Summarize:
The key to tail recursion is that recursive calls are the last step in the function, allowing the compiler to optimize recursion into a loop, thereby avoiding stack overflow problems. Satisfied with recursive calls is the last step in the function, and the result can be returned directly without creating a new stack frame, wasting the stack space leads to a burst.
The above is the detailed content of Java using Scala to implement tail recursive optimization to solve the problem of explosive stacks. For more information about Java Scala tail recursive optimization, please pay attention to my other related articles!