1. Background

In the daily development process, it is inevitable to use recursive operation sometimes. But we all know that in recursive functions, we will call ourselves. If the level is large enough to exceed the depth of the stack, it will lead to stack overflow. Therefore, many companies have an iron rule to avoid using recursive functions in projects, so many colleagues have replaced recursive operations with circular operations to solve the problem of stack overflow.

So let's think about it. How can recursive operations not cause stack overflow? Let's implement a small example: write a function and calculate the function's continuous addition operation For example, if you pass in 10, the result of 1 + 2 + 3 + 4 +... + 10 will be returned.

2. Common recursion

Here we use ordinary recursive function to realize.

private static int recursionEvenAdd(int i) {
    System.out.println("current i="+i);
    if (i <= 0) {
        return 0;
    } else {
        return i + recursionEvenAdd(i - 1);
    }
}


//Write a main function to test
public static void main(String[] args) {
    System.out.println(recursionEvenAdd(10));
}

When I pass in 10, I get the result

When I introduced 7000. It turned out to be embarrassing.

Obviously, when i dropped from 7000 to 967, which is 6033 cycles, the stack overflowed.

3. Tail recursion

① . using tail recursion

/**
  *
  * @param r The last calculation result needs to be executed manually for the first time
  * @param i Calculation factor
  * @return results of enforcement
  */
private static int tailRecursionEvenAdd(int i, int r) {
    System.out.println("current i="+i);
    if (i <= 0) {
        return r;
    } else {
        return tailRecursion1(i - 1, i + r);
    }
}

//Write a main function to test
public static void main(String[] args) {
    System.out.println(tailRecursionEvenAdd(7000,0));
}

The test found that the stack overflowed, which is consistent with the above results.

② . tail recursion difference

We can compare the difference between tail recursion and ordinary recursion in function writing. There is no egg to use, so the optimization of tail recursion depends on the implementation mechanism of tail recursion optimization added to the compiler.

Obviously, after the above tests, Java 8 (my environment is java 1.8) has not been optimized. After my understanding. In c, c, tail recursion is optimized.

③ . compiler to optimize tail recursion.

In short, it means that reusing the same stack frame, not only does not need to release the previous one, but also does not need to open the next one, which is very efficient (some people do experiments, which is more efficient than recursion and iteration).

4. Implement tail recursion in JAVA

Since there is no optimization of tail recursion in java8, can't we? In fact, it can be realized. Direct code:

@FunctionalInterface
public interface TailRecursion<T> {
    /**
     * For connection between recursive stack frames, lazy evaluation
     *
     * @return Next recursive stack frame
     */
    TailRecursion<T> apply();

    /**
     * Determine whether the current recursion ends
     *
     * @return The default is false, because normal recursion is not finished yet
     */
    default boolean isFinished() {
        return false;
    }

    /**
     * The result of recursion can only be called at the end of recursion. The default exception is given here. The value is obtained by rewriting the tool class
     *
     * @return Recursive end result
     */
    default T getResult() {
        throw new Error("Recursion is not over,Call get result exception!");
    }

    /**
     * Evaluate as early as possible and perform a series of recursions. Because there is only one stack frame, findFirst is used to get the final stack frame, and then getResult method is called to get the final recursion value
     *
     * @return Evaluate early to get the final recursive result
     */
    default T invoke() {
        return Stream.iterate(this, TailRecursion::apply)
                .filter(TailRecursion::isFinished)
                .findFirst()
                .get()
                .getResult();
    }
}



public class TailInvoke {
    /**
     * Get the next recursion of the current recursion
     *
     * @param nextFrame Next recursion
     * @param <T>       T
     * @return Next recursion
     */
    public static <T> TailRecursion<T> call(final TailRecursion<T> nextFrame) {
        return nextFrame;
    }

    /**
     * End the current recursion, rewrite the value of the corresponding default method, change the completion status to true, set the final return result, and set the illegal recursion call
     *
     * @param value Final recursive value
     * @param <T>   T
     * @return A tail recursion of the isFinished state true. The external part starts the recursion evaluation by calling the invoke method of the interface to evaluate as early as possible.
     */
    public static <T> TailRecursion<T> done(T value) {
        return new TailRecursion<T>() {
            @Override
            public TailRecursion<T> apply() {
                throw new Error("Recursion has ended,Illegal call apply Method");
            }

            @Override
            public boolean isFinished() {
                return true;
            }

            @Override
            public T getResult() {
                return value;
            }
        };
    }
}

Tail recursion usage test:

/**
 * stream.iterate is used to implement tail recursion without stack overflow, and natural multithreading. The ForkJoinPool used by stream will not cause high CPU share (at most 1 core)
 *
 * @param r The last calculation result needs to be executed manually for the first time
 * @param i Calculation factor
 * @return results of enforcement
 */
private static TailRecursion<Integer> tailRecursionEvenAdd(int i, int r) {
    log.debug("{} execute : {} , {}", Thread.currentThread().getName(), i, r);
    if (i <= 0) {
        return TailInvoke.done(r);
    } else {
        return TailInvoke.call(() -> tailRecursion2(i - 1, i + r));
    }
}

//Write a main function to test
public static void main(String[] args) {
    System.out.println(tailRecursionEvenAdd(7000,0).invoke());
}

As you can see, the stack overflow will not occur. If I pass 10000 later, the stack overflow will not occur. Is it very fragrant. ha-ha.

5. Comparison and summary

After comparison, we find that tail recursion is relatively complex. How to choose between them when developing? In fact, for some recursion operations, we already know in advance that the depth is two or three layers, and the amount of data is not large. In this case, we still recommend using common recursion or direct loop operations. Therefore, it can be seen that many company specifications can use loops without recursion, which is also very reasonable.