This article is participating in “Java Theme Month – Java Debug Notes Event”, see < Event link > for more details.

preface

A few days ago, some friends in the group had a discussion as follows:

【 Xi 'an -Java- Xiao Bai 】 Who met? [Hangzhou-Java-Joel] you want to interrupt the point to see which line is wrong [Xi 'an -Java- xiaobai] stack overflow, mybatis to execute the query, circular query, 1000 queries a time, To more than 160 times when stack overflow [Beijing -Android- back] do you have recursion [Xi 'an-java - xiao Bai] mm. I just got rid of the recursion. Let's try a loop. 【 Beijing-android-back 】 @xian-android-back 】 < Beijing -android-back > < Beijing -android-back > < Beijing -android-back > < Beijing -android-back > < Beijing -android-back > < Beijing -android-back > < Beijing -android-back > Will give us the result [Xi 'an -Java- xiabai] feel the speed is much faster than the recursive [Hangzhou -Java-JOEL] query batch to check a little better [Beijing -Android- back] recursive method in the body of the variable will always be saved, but some variables do not have any meaning. By looping, the variables in the method body are recycled instead of occupying memory all the time. 【 Xian-Java-xcBeyond 】 stack, mainly used to store the stack frame, each execution of a method will appear to push the stack operation, so the use of recursion when the generation of stack frame more, Recursion is going to affect memory, it's going to consume memory. With a loop, you execute a method that pushes only one stack frame at a time, so it saves memory.Copy the code

It’s all recursion! So let’s talk about recursion and loops, how to use them, and what are the differences between them? Time complexity, space complexity

Circular, recursive validation

  • cycle: Performs an operation repeatedly (loop body) when a condition is met. Such as:for,whilecycle
  • Recursion: Call the method itself within a method with the judgment that the recursion is over.

Loops and recursion can be implemented interchangeably, but they are very different from each other in time complexity and space complexity.

Next, let’s just pull up the code to see what happens, taking an integer that decrement to 0 as an example.

package com.xcbeyond.test;	
 
	
/** * recursive test *@Auther: xcbeyond	
 * @Date: 2019/9/12 11:26 * /	
public class RecursionTest {	
 
	
    public static void main(String [] args) {	
        int number = 5000;	
 
	
        long startTime = System.currentTimeMillis();	
        loop(number);	
        long endTime = System.currentTimeMillis();	
        System.out.println();	
        System.out.println("Cycle time:" + (endTime-startTime));	
 
	
 
	
        long startTime2 = System.currentTimeMillis();	
        recursion(number);	
        long endTime2 = System.currentTimeMillis();	
        System.out.println();	
        System.out.println("Recursive time:" + (endTime2-startTime2));	
    }	
 
	
    /** * recursive *@param n	
     * @return* /	
    public static void recursion(int n) {	
        if(n <= 0) {	
            return;	
        }else {	
            System.out.print(n + "");	
            recursion(n - 1); }}/** * loop *@param n	
     * @return* /	
    public static void loop(int n) {	
        for(int i = n; i> 0; i--) { System.out.print(i +""); }}}Copy the code

Results analysis:

The number is 1000, 5000, and 10000 respectively. The time result is as follows:

Situation 1:1000

Cycle time: 34 Recursion time: 18Copy the code

Situation 2:500

Cycle time: 48 Recursive time: 11Copy the code

Case 3:10,000

Cycle time: 142 Exception in thread "main" java.lang.StackOverflowError at sun.nio.cs.UTF_8$Encoder.encodeLoop(UTF_8.java:691) at java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:579) at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:271) at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:125) at java.io.OutputStreamWriter.write(OutputStreamWriter.java:207) at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:129) at java.io.PrintStream.write(PrintStream.java:526) at java.io.PrintStream.print(PrintStream.java:669) at com.xcbeyond.test.RecursionTest.recursion(RecursionTest.java:36)Copy the code

From the above results, the recursive algorithm is more time-consuming than the recursive algorithm, but when the number of loops and recursions reaches a certain data level, the recursive algorithm will have StackOverflowError, which is the phenomenon described in the beginning of the article.

For stack overflow problem, we can further trace as follows:

(The above code is slightly modified, and the number is set to 5 for easy observation)

package com.xcbeyond.test;	
 
	
/** * recursive test *@Auther: xcbeyond	
 * @Date: 2019/9/12 11:26 * /	
public class RecursionTest {	
 
	
    public static void main(String [] args) {	
        int number = 3;	
 
	
        long startTime = System.currentTimeMillis();	
        loop(number);	
        long endTime = System.currentTimeMillis();	
        System.out.println();	
        System.out.println("Cycle time:" + (endTime-startTime));	
 
	
 
	
// long startTime2 = System.currentTimeMillis();
// recursion(number);
// long endTime2 = System.currentTimeMillis();
// System.out.println();
// system.out. println(" endTime2: "+ (endTime2-startTime2));
    }	
 
	
    /** * recursive *@param n	
     * @return* /	
    public static void recursion(int n) {	
        Thread.currentThread().dumpStack();	
        if(n <= 0) {	
            return;	
        }else {	
            System.out.print(n + "");	
            recursion(n - 1); }}/** * loop *@param n	
     * @return* /	
    public static void loop(int n) {	
        for(int i = n; i> 0; i--) { System.out.print(i +""); Thread.currentThread().dumpStack(); }}}Copy the code

Loop stack allocation:

Recursive stack allocation:

By analyzing the stack loading and unloading process, the loop will only stack once, while the recursion will accumulate the stack several times, that is, as the recursion number increases, the problem of stack overflow will occur.

Cyclic, recursive distinction

  • cycle
    • Advantages: Simple structure
    • Cons: Doesn’t solve every problem. Some problems are suitable for recursion rather than loops, and loops are best used if they are not too difficult to use.
  • recursive
    • Advantages: The code is concise, clear, and easy to verify correctness
    • Disadvantages: Its operation requires a large number of method calls, if the call layer is deep, need to add additional stack processing, such as parameter passing need to stack operations, will have a certain impact on the execution efficiency. However, for some problems, it would be extremely ugly code to not use recursion.

Algorithms that can be handled by general recursive calls are also solved through loops that often require additional inefficient processing. Today’s compilers are optimized to handle methods that are called multiple times more efficiently than loops.

conclusion

Each recursion is each call to the method, i.e., multiple stack operations. So, if you use a recursive algorithm, you can’t recurse too much, because complexity will cause stack overflow.

Stack is mainly used to store stack frames. Every time a method is executed, there will be a stack pressing operation. Therefore, when using recursion, there will be more stack frames, which will affect the memory and consume the memory very much. With a loop, you execute a method that pushes only one stack frame at a time, so it saves memory.

In short, the following principles can be followed in the selection of cyclic and recursive algorithms:

  • The number of cycles is not particularly large, and the processing logic is extremely complex. If the cycle algorithm is used, it may be difficult to understand, the recursive algorithm can be preferred.
  • If the processing logic is simple, use a loop.

One thing to remember, whether you use loops or recursion, is to avoid scenario processing that has too many loops. Avoid it.