Java - Understanding Recursion

Question

Can someone please explain to me why this prints out 1 2 3 4 5? I figured it would print out 4 3 2 1 0 but my book and eclipse both say I'm wrong.

public class whatever {

    /**
     * @param args
     */
    public static void main(String[] args) {
        xMethod(5);

    }

    public static void xMethod(int n){
        if (n>0){
            xMethod(n-1);
            System.out.print(n + " ");
        }
    }


}

Answer 1

It is pretty simple, these are the calls

main
   xMethod(5)
      xMethod(4)
          xMethod(3)
             xMethod(2)
                 xMethod(1)
                     xMethod(0)
                 print 1
             print 2
          print 3
      print 4
  print 5

So you see the prints are 1,2,3,4,5

Answer 2

It's the result of the call stack. Here's what it would look like after a call with n = 5. Rotate your head about 180 degrees, since the bottom of this call chain is actually the top of the stack.

• xMethod(5)
  • xMethod(4)
    • xMethod(3)
      • xMethod(2)
        • xMethod(1)
          • xMethod(0)

In a recursive call, you have two cases - a base case and a recursive case. The base case here is when n == 0, and no further recursion occurs.

Now, what happens when we start coming back from those calls? That is, what takes place after the recursive step? We start doing System.out.print(). Since there's a condition which prevents both recursion and printing when n == 0, we neither recurse nor print.

So, the reason that you get 1 2 3 4 5 as output is due to the way the calls are being popped from the stack.

Answer 3

It first call itself recursively and only when the recursive call finishes it prints. So think about which call finishes first - it's when n = 0. Then n = 1, etc.

It's a stack and you print after taking from the stack (after the recursion call), so the order is reversed. If you printed before putting on the stack, then the order is preserved.