In simple terms, recursion is simply calling itself, passing in a different variable each time. Recursion helps solve complex problems while keeping code simple. I’ve covered recursion briefly in previous articles, but now I want to take a closer look at the invocation mechanism of lower recursion.

First, recursive call mechanism

Let’s start with a simple recursive call:

package recursion; public class RecursionTest { public static void main(String[] args) { test(4); } public static void test(int n) { if (n > 2) { test(n - 1); } System.out.println("n=" + n); }}Copy the code

As you can see, in the main method, test(4) is executed. If n>2 is satisfied, test() continues to call test() until the recursion condition is not satisfied and the value of n is printed. The results are also easy to imagine:

n=2
n=3
n=4

Process finished with exit code 0
Copy the code

So instead of focusing on the results, let’s take this code and draw a picture to see how this recursively works.



These are some of the things that happen in the JVM during code execution. However, some of the descriptions of the JVM may not be accurate, and this is just a reminder.

  1. First, in the runmainMethod opens a stack frame for the main method.

    When called in the main methodtestMethod, a stack frame is pushed. When a method is not finished running, it does not exit the stack.

    So, runtest(4), will continue to push a stack frame (red arrow).
  2. intest(4), will continue to call after judgmenttest(3), and continues to press a stack frame.
  3. intest(3), will continue to call after judgmenttest(2), and continues to press a stack frame.
  4. intest(2)In, after judging that it is no longer recursive, I run print code to print outnIs 2.

    When the method is finished, it exits the stack (yellow arrow) and returns totest(3).
  5. test(3)Print out the value of n as3, continue to exit the stack, returnThe test (4).
  6. test(4)Print out the value of n as 4,mainMethod ends, exit the program.

So, the result of the code run is 2,3,4.

Second, use recursion need to know points

  1. When a method is executed, a new protected independent space is created. Like the stack frame above.
  2. The local variables of a method are independent and do not affect each other. Let’s say the variables that we recurse to each timen.

    However, if a reference type variable is used in a method, that reference type is shared. For example, reference an array.
  3. Focus on: Recursion must approach the condition of exit recursion, otherwise it recurses indefinitely and eventually the stack overflowsStackOverflowError.
  4. When the method completes execution, or encountersreturn, will return. The result is returned to whoever calls.

    Take the top stack frame in the image abovetest(2)When it’s done, it returns to the one that called ittest(3).