CODEWITHSUNDEEP
javarecursion
Nabeel A.Rahman
Nabeel A.Rahman

Reputation: 301

Recursion: I don't understand why the code will print out n integers 1,2,3,4,5

My expected result was that is not going to print anything

In the example below if I try to read the code xMethod(5) as it is a recursive function when =0 i.e. xMethod(0) I was expecting that it should not get into the if statement.

My expectation for this code was that there should not be an output since the print statement is after the recursive method

public class recursionThree {

    public static void main(String[] args) {
        xMethod(5);
    }

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

Upvotes: 2

Views: 166

Answers (5)

Henry
Henry

Reputation: 43788

The best way to understand recursion is to regard the recursive calls as black box doing what they are supposed to do.

So your xMethod prints the numbers 1 to n. It does this, by first printing the numbers 1 to n-1 (using the recursive call) and then printing the number n.

Upvotes: 0

陈敏华
陈敏华

Reputation: 1505

in your code, the stack will generate 5 frame for these 5 recursive calls of xMethod. Before each call finished, System.out.print(n + " ") can print the variable n in the frame. your memory stack looks like this

 ---------
|   n=1   |
 ---------
|   n=2   |
 ---------
|   n=3   |
 ---------
|   n=4   |
 ---------
|   n=5   |
 ---------

every box is a frame, and each frame will be cleaned from top to bottom, so the output would be 1 2 3 4 5

Upvotes: 0

Sweeper
Sweeper

Reputation: 273380

Methods don't just get called and not return. They return to the caller.

As you may know, methods, when called, are pushed onto a call stack. So when you call xMethod(5), it calls xMethod(4), and that calls xMethod(3)... creating a call stack like this:

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

Now what does xMethod(0) do? It does not go into the if statement so it returns immediately. When a method returns, it is popped from the call stack, and control is back at the next thing in the stack. Now we have:

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

Remember we are still at the xMethod(n-1); line in the xMethod(1) stack frame? Since xMethod(n-1) returned, we can continue to run the rest of the code. Therefore, System.out.print is called with n being 1 (we are still in the xMethod(1) stack frame!).

Now xMethod(1) finishes running and returns and is popped from the stack. Control is back at xMethod(2). And the cycle continues on, until xMethod(5) returns.

Upvotes: 0

anurag0510
anurag0510

Reputation: 763

It's very simple actually.

If we call some function within another function then control returns back to same function once the called function completes it's execution.

In your case as n == 0 the called function returns control back to calling function hence printing 1,2,3,4,5.

Upvotes: 1

Erwin Bolwidt
Erwin Bolwidt

Reputation: 31299

You need to step through the program:

  • Calling xMethod(5) from main
    • n > 0, so it calls xMethod(4)
      • n > 0, so it calls xMethod(3)
        • n > 0, so it calls xMethod(2)
          • n > 0, so it calls xMethod(1)
            • n > 0, so it calls xMethod(0)
              • n not > 0, so it returns without doing anything
            • It prints "1"
          • It prints "2"
        • It prints "3"
      • It prints "4"
    • It prints "5"
    • Done.

Upvotes: 2

Related Questions