how recursive function works level by level?

I have trouble on understating how recursion works, I have been struggling this for a while! Could anyone can help me with this? I’d really appreciate that, and here is the code for instance:

public int recur(int m) {   
    if(m == 0) {
        return 2;
    }
    int k = 0;
    System.out.println("The K before is"+ k+" m is:"+m);
    k = recur(m - 1)+1;
    System.out.println("The K AFTER is"+ k+" m is:"+m);
    return k;
}

when we pass 3 into the function, the output will be:

The K before is0 m is:3
The K before is0 m is:2
The K before is0 m is:1
The K AFTER is3 m is:1
The K AFTER is4 m is:2
The K AFTER is5 m is:3

Since the recursion call is between two printings, I guess the way how it works is the function will:

1. Execute code before the recursion call.
2. Then it will not go through the code below the recursion call and stop right there.
3. Jump back to the beginning of the method.
4. After everything before the recursion call is finished, the program will continue to execute the code after the recursion call.

Is this the correct concept? Or could anyone explain this? Really appreciate that!

Answer

First thing you have to understand about recursion is that you are executing the same method but you aren’t jumping around in it. You get different executions. Let’s start simple without recursion:

public void a() {
  System.out.println(">> before b()");
  b();
  System.out.println("<< after b()");
}

public void b() {
  System.out.println(">>>> in b() <<<<");
}

When you call a() that will:

1. Print >> before b().

2. Call b().

3. Print >>>> in b() <<<<.

4. Finish the execution of b().

5. Go back to a() and print << after b().

6. Finish the execution of a().

So when you call a method the current one waits for the call to finish and then continues. The call to b() is nested in a().

In the case of recursion the same thing happens but instead of a different method, you call the same one. You essentially get different versions of the method executing and waiting, you don’t jump around the same one. So, with a recursive call you get something like this:

1. You call recur(3) and the method executes.

2. It prints The K before is0 m is:3

3. The method calls recur(2) which is a recursive call. At this point you get the following state:

public int recur(int m) {/* m = 2 */
    if(m == 0) {
        return 2;
    }
    int k = 0;
    System.out.println("The K before is"+ k+" m is:"+m);
    k = recur(m - 1)+1; // <-- stop and wait for this to finish
    System.out.println("The K AFTER is"+ k+" m is:"+m);
    return k;
}

4. Now you get a brand new copy of the method execution. This is called as recur(2).

5. It prints The K before is0 m is:2

6. The method calls recur(2) which is a recursive call. At this point you get the following state:

public int recur(int m) {/* m = 3 */                             | public int recur(int m) {/* m = 2 */
    if(m == 0) {                                                 |     if(m == 0) {
        return 2;                                                |         return 2;
    }                                                            |     }
    int k = 0;                                                   |     int k = 0;
    System.out.println("The K before is"+ k+" m is:"+m);         |     System.out.println("The K before is"+ k+" m is:"+m);
    k = recur(m - 1)+1; /*<-- still waiting for this to finish*/ |     k = recur(m - 1)+1; // <-- stop and wait for this to finish
    System.out.println("The K AFTER is"+ k+" m is:"+m);          |     System.out.println("The K AFTER is"+ k+" m is:"+m);
    return k;                                                    |     return k;
}                                                                | }

7. Now you get a brand new copy of the method execution. This is called as recur(1).

8. It prints The K before is0 m is:1

9. The method calls recur(0) which is a recursive call. At this point you get the following state:

public int recur(int m) {/* m = 3 */                             | public int recur(int m) {/* m = 2 */                             | public int recur(int m) {/* m = 1 */
    if(m == 0) {                                                 |     if(m == 0) {                                                 |     if(m == 0) {
        return 2;                                                |         return 2;                                                |         return 2;
    }                                                            |     }                                                            |     }
    int k = 0;                                                   |     int k = 0;                                                   |     int k = 0;
    System.out.println("The K before is"+ k+" m is:"+m);         |     System.out.println("The K before is"+ k+" m is:"+m);         |     System.out.println("The K before is"+ k+" m is:"+m);
    k = recur(m - 1)+1; /*<-- still waiting for this to finish*/ |     k = recur(m - 1)+1; /*<-- still waiting for this to finish*/ |     k = recur(m - 1)+1; // <-- stop and wait for this to finish
    System.out.println("The K AFTER is"+ k+" m is:"+m);          |     System.out.println("The K AFTER is"+ k+" m is:"+m);          |     System.out.println("The K AFTER is"+ k+" m is:"+m);
    return k;                                                    |     return k;                                                    |     return k;
}                                                                | }                                                                | }

10. Now you get a brand new copy of the method execution. This is called as recur(0).

11. This time the execution goes inside the if statement, since the condition is fulfilled. Final state before everything resolves:

public int recur(int m) {/* m = 3 */                             | public int recur(int m) {/* m = 2 */                             | public int recur(int m) {/* m = 1 */                             | public int recur(int m) {/* m = 0 */
    if(m == 0) {                                                 |     if(m == 0) {                                                 |     if(m == 0) {                                                 |     if(m == 0) {
        return 2;                                                |         return 2;                                                |         return 2;                                                |         return 2; // <-- return and finish
    }                                                            |     }                                                            |     }                                                            |     }
    int k = 0;                                                   |     int k = 0;                                                   |     int k = 0;                                                   |     int k = 0;
    System.out.println("The K before is"+ k+" m is:"+m);         |     System.out.println("The K before is"+ k+" m is:"+m);         |     System.out.println("The K before is"+ k+" m is:"+m);         |     System.out.println("The K before is"+ k+" m is:"+m);
    k = recur(m - 1)+1; /*<-- still waiting for this to finish*/ |     k = recur(m - 1)+1; /*<-- still waiting for this to finish*/ |     k = recur(m - 1)+1; /*<-- still waiting for this to finish*/ |     k = recur(m - 1)+1;
    System.out.println("The K AFTER is"+ k+" m is:"+m);          |     System.out.println("The K AFTER is"+ k+" m is:"+m);          |     System.out.println("The K AFTER is"+ k+" m is:"+m);          |     System.out.println("The K AFTER is"+ k+" m is:"+m);
    return k;                                                    |     return k;                                                    |     return k;                                                    |     return k;
}                                                                | }                                                                | }                                                                | }

12. Finally, nested calls are resolved from the inside out.

13. recur(0) finishes. Returns 2. Computing the result of recur(0)+1 can finally continue and assign that result k. State now:

public int recur(int m) {/* m = 3 */                             | public int recur(int m) {/* m = 2 */                             | public int recur(int m) {/* m = 1 */
    if(m == 0) {                                                 |     if(m == 0) {                                                 |     if(m == 0) {
        return 2;                                                |         return 2;                                                |         return 2;
    }                                                            |     }                                                            |     }
    int k = 0;                                                   |     int k = 0;                                                   |     int k = 0;
    System.out.println("The K before is"+ k+" m is:"+m);         |     System.out.println("The K before is"+ k+" m is:"+m);         |     System.out.println("The K before is"+ k+" m is:"+m);
    k = recur(m - 1)+1; /*<-- still waiting for this to finish*/ |     k = recur(m - 1)+1; /*<-- still waiting for this to finish*/ |     k = recur(m - 1)+1; // <-- recur(m - 1) = 2
    System.out.println("The K AFTER is"+ k+" m is:"+m);          |     System.out.println("The K AFTER is"+ k+" m is:"+m);          |     System.out.println("The K AFTER is"+ k+" m is:"+m);
    return k;                                                    |     return k;                                                    |     return k;
}                                                                | }                                                                | }

14. The K AFTER is3 m is:1 is printed.

15. recur(1) finishes. Returns 3. Computing the result of recur(1)+1 can finally continue and assign that result k. State now:

public int recur(int m) {/* m = 3 */                             | public int recur(int m) {/* m = 2 */
    if(m == 0) {                                                 |     if(m == 0) {
        return 2;                                                |         return 2;
    }                                                            |     }
    int k = 0;                                                   |     int k = 0;
    System.out.println("The K before is"+ k+" m is:"+m);         |     System.out.println("The K before is"+ k+" m is:"+m);
    k = recur(m - 1)+1; /*<-- still waiting for this to finish*/ |     k = recur(m - 1)+1; // <-- recur(m - 1) = 3
    System.out.println("The K AFTER is"+ k+" m is:"+m);          |     System.out.println("The K AFTER is"+ k+" m is:"+m);
    return k;                                                    |     return k;
}                                                                | }

16. The K AFTER is4 m is:2 is printed.

17. recur(2) finishes. Returns 4. Computing the result of recur(2)+1 can finally continue and assign that result k. State now:

public int recur(int m) {/* m = 3 */
    if(m == 0) {
        return 2;
    }
    int k = 0;
    System.out.println("The K before is"+ k+" m is:"+m);
    k = recur(m - 1)+1; // <-- recur(m - 1) = 4
    System.out.println("The K AFTER is"+ k+" m is:"+m);
    return k;
}

18. The K AFTER is5 m is:3 is printed.

19. The initial call to recur(3) finishes.

So, each call to a method which is initiated from another method will initiate a nested execution. The execution then resolves inner first then continues with the outer ones. Each call has its own state – if you follow along in the debugger it would seem like the execution moves to the start of the method but in reality you are now in a completely different execution that’s different to the old one.