Java 8 uses lambda to implement Java tail recursion

preface

What this article introduces is not new knowledge, but the comprehensive application of some knowledge explained earlier. As we all know, recursion is a very effective way to solve complex problems and the core of functional languages. In some functional languages, there is no concept of iteration and while, because such loops can be implemented by recursion. Compilers of such languages optimize the tail recursion form of recursion, while Java compilers do not, This article is about to complete such an optimization of tail recursion.

What is tail recursion

This article will use the simplest factorial calculation in recursion as an example

Recursive implementation

This method can easily overflow the stack when calculating a large number of factorials. The reason is that the previous variables need to be saved in the stack every time the next round of recursion is called, so the whole stack structure is similar

5 4 3 2 1 ------------------->

Stack depth

Those intermediate variables will be saved until they are recursive to the end, so each recursion needs to open up a new stack space

Tail recursive implementation

The tail recursive version of any recursion is very simple. The reason for analyzing the stack overflow above is that a variable will be attached to each return, so you only need not attach this variable to the return. It's easy to say. What should I do? In fact, it's also very easy. We use a parameter to save the results of the last round of recursion, so it's OK. Therefore, the factorial implementation of tail recursion should be such code.

Use a factorial variable to save the value calculated by the last factorial round, so there is no need to save the variable when returning. The whole calculation process is (5 * 4) 20 - > (20 * 3) 60 - > (60 * 2) 120 - > return 120

In this way, the current stack space is refreshed and the stack is reused after each round of recursion, which overcomes the stack overflow problem of recursion. A return like this is written recursively without any variables, that is, recursion occurs at the end of the function, which is called 'tail recursion'.

Compiler optimization using lambda

Obviously, if things are so simple, this article will be over, and it has nothing to do with lambda:) however, when you call the tail recursion method above, you find that it has no effect. If the stack overflows, it will still overflow. In fact, I said at the beginning that the tail recursion method itself is not useful, It depends on the compiler's optimization of tail recursion. In many languages, the compiler optimizes tail recursion. However, these languages do not include Java. Therefore, here we use lambda's lazy loading (lazy evaluation) mechanism to delay the call of recursion, so as to realize the reuse of stack frames.

Design tail recursive interface

Therefore, we need to design such a function interface to replace the stack frame in recursion, and complete the connection between each stack frame through the function method of apply (named apply because the parameter of the method is a stack frame and the return value is also a stack frame, similar to the apply of the function interface). In addition, We also need to define several methods to enrich the tail recursive interface.

Apply (connect stack frame, lazy evaluation) judge whether the recursion ends, get the final result of recursion, and execute recursion (evaluation as soon as possible)

According to the above definitions, the following tail recursive interface is designed

Design an externally unified tail recursive wrapper class

In order to achieve the effect of reusability, a tail recursion wrapper class is designed here to unify external methods, so that tail recursion can be completed by calling the same method without considering the internal implementation details, because all recursive methods are composed of only two types of elements, one is how to call the next recursion, and the other is the termination condition of recursion, Therefore, the packaging method is designed as the following two

Call next recursion

End this round of recursion

The code is as follows

Tail recursive function to complete factorial

By using the tail recursive interface and wrapper class above, you can easily write the tail recursive function by calling the wrapper call and done. The code is as follows

It is found that as like as two peas recursion methods originally used, the call and done methods of wrapper class are used to represent recursive calls and ends.

Expected tail recursion

Test tail recursive function

Here is an explanation, because if the factorial calculation needs to calculate the stack overflow, generally, the data type of Java needs to be wrapped with BigInteger. In order to simplify the code, the test here is only to test whether the stack will overflow. Therefore, we change the * of the operator to + so that the result is only smaller, but the depth of the stack does not change. The test code is as follows

First, test ordinary recursion with a depth of 10W

Test code

Of course, the stack overflowed

Here we test the tail recursion of 1000W stack frames

Tail recursive code

Test code

It was found that the results worked well

Since the initial value of factorial calculation is generally 1, wrap it further and set the initial value to 1

The final calling code is as follows, completely shielding the implementation details of tail recursion

summary

This paper explains that the stack frame reuse in recursion is completed by using the lazy loading feature of lambda, and the 'tail recursion' optimization of functional language compiler is realized. Although the above example is very simple, the designed interface and packaging classes are universal. It can be said that anyone who needs to use tail recursion can use the above code to realize the optimization of tail recursion, This is a little help for the compiler.

The above is what Xiaobian introduced to you. Java8 uses lambda to realize java tail recursion. I hope it will be helpful to you. If you have any questions, please leave me a message and Xiaobian will reply to you in time. Thank you very much for your support for the programming tips website!