Why does the following recursive program give the following output

Question

I am trying to understand the java recursion from beginning. I came through a following example

public static void main(String[] args) {
  threeWays(1,4);
}

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

gives the output

1=4
2=3
3=2
4=1
5=0
4=0
3=1
4=0
2=2
3=1
4=0
3=0

I understand up to 5=0 but why does the program run beyond that? Why doesn't it stop once n becomes -1? Where does 4=0 come from? I don't even know what to call this phenomenon so the question might look vague. Any help would be appreciated.

Answer 1

threeWays(id+1,n-1); // when this returns,
threeWays(id+1,n-2); // ... the program still does this

You are recursively calling the function twice. So after it reaches the end for the first call, it unwinds the stack a little and then goes into the second recursion.

And from that second call, it branches out twice again at each layer.

If this is confusing, it could be illustrative to step through the program in a debugger. You can see each frame in the call stack there, including the local variables and which line of code they are in right now.