Explain Recursion Output

Question

public class Main {
    public static void main(String[] args) {
        splitIt(1, 3);
    }

    public static void splitIt(int id, int n) {
        if (n > 0) {
            splitIt(id + 1, n - 1);
            System.out.println(id + "=" + n);
            splitIt(id + 1, n - 1);
        }
    }
}

When I run this code I get the output below and I do not understand why and how I am getting that output. If someone could please explain that would be appreciated.

3=1
2=2
3=1
1=3
3=1
2=2
3=1

I tried using the debugger but I still do not understand.

Answer 1

You need to make a chart with id and n and follow the logic. As each call is made, write down the values. Once called, the method will not return until n <= 0 which is implicitly invoked at the end of a void method (or earlier with with an explicit return;).

A key point to remember is that arguments are stored on the call stack and printed in reverse order when the call returns.

Try running the following with the additional print statements to see what is going on. The *'d print statements print the same values you printed in your original code.

public static void main(String[] args) {
     splitIt(1, 3);
 }

 static boolean reason_nle0;
 public static void splitIt(int id, int n) {
     System.out.printf("first entered: id = %d, n = %d%n", id, n);
     reason_nle0 = true;
     if (n > 0) {
         System.out.printf("making call1 with - id = %d, n = %d%n", id, n);
         splitIt(id + 1, n - 1); // call1
         System.out.printf("*return from  call1, printing - id = %d, n = %d%n", id, n); 
         System.out.printf("making call2 with - id = %d, n = %d%n", id, n);
         splitIt(id + 1, n - 1); // call2
         System.out.printf("after call2 - id = %d, n = %d%n", id, n);
         reason_nle0 = n <= 0;
     }
     System.out.println(reason_nle0 ? "return since n <= 0" : "fall thru");
 }