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

To explain how recursion works, let's see the sample of factorial calculation:

int factorial(int i) {
    if (i == 0) {
        return 1;
    }
    return i * factorial(i - 1);
}

For example let's get factorial value of 5:

int result = factorial(5);

Remember that exit value:

if (i == 0) {
   return 1;
}

and return value:

i * factorial(i - 1)

Just look at iterations (according to return value):

5*factorial(4) -> 4*factorial(3) -> 3*factorial(2) -> 2*factorial(1) -> 1*factorial(0)

In fact it is:

5*(4*(3*(2*(1*factorial(0)))))

cause factorial(4) == 4*factorial(3), factorial(3) == 3*factorial(2), etc.

last iteration is factorial(0) that equals 1 (look at exit value).

In result:

5*(4*(3*(2*(1*1)))) = 120

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

System.out.print(n + " ");
xMethod(n-1);

It will print 5 4 3 2 1. Because It will first print then call xMethod.

And in your case

xMethod(n-1);
System.out.print(n + " ");

Here it will reach to end condition then poped up and print. so 1 2 3 4 5

Answer 4

xMethod is called until n is 0. The stack will then be xMethod(5)->xMethod(4)->xMethod(3)->xMethod(2)->xMethod(1)->xMethod(0). As it finishes xMethod(0), it will pop into the next line in xMethod(1), printing 1. This will then repeat until xMethod(5) is exited.

If you went and expanded each xMethod as it was called, the code would look something like this:

{
    nA = 5 // What n was set at first
    if (nA>0){
        { 
            // Instead of xMethod(n-1), 
            // we're setting nB to nA - 1 and 
            // running through it again.
            nB = nA - 1  // nB is 4

            if (nB>0){
                { 
                    nC = nB - 1 // nC is 3
                    if (nC>0){
                        { 
                            nD = nC - 1 // nD is 2
                            if (nD>0){
                                {
                                    nE = nD - 1 // nE is 1
                                    if (nE>0){
                                        {
                                            nF = nE - 1 // nF is 0.
                                            if (nF>0){
                                                // This will never execute b/c nF is 0.
                                            }
                                        }
                                        System.out.print(nE + " "); // prints 1
                                    }
                                }
                                System.out.print(nD + " "); // prints 2
                            }
                        }
                        System.out.print(nC + " "); // prints 3
                    }
                }
                System.out.print(nB + " "); //prints 4 
            }
        }
        System.out.print(nA + " "); //prints 5
    }
}

Answer 5

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.

Answer 6

   1 public static void xMethod(int n){
   2    if (n>0){ //the base condition
   3         xMethod(n-1); //function is again called with one value less than previous
   4         System.out.print(n + " "); //now print
   5     }
   6  }

Now look at line#3, As nothing is printed but the function is again called, so from line#3, the call reaches to line#1 again. which means, n was 5, but the new call takes n = 4 and it keeps going till line#2 tells that n is now less than 0.

When if condition fails at line#2, it reaches at line#5 and then line#6 which means the function has ended execution, and n = 1 at this time.

Now where should the call be returned? at line#3 where the last function was called and it will be popped out from stack executing line#4 which prints the value of n i.e. 1 2 3 4 5.

Answer 7

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 8

this xMethod(n-1); System.out.print(n + " ");

should be:

        System.out.print(n + " ");
        xMethod(n-1);

Answer 9

this is the right code

System.out.print(n + " ");
xMethod(n-1);