java recursion

[Kasun Wixkramanayake]

public void x(int n) {

        for (int i = 0; i < n; i++) {


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

 

can you tell me how this recursion works.

[Tim Cooke]

Are you asking about how recursion works in general? If so then have a read of the Wikipedia: Recursion page.

If not, then exactly what are you asking?

[Kasun Wixkramanayake]

no i know how the recursion work but i don not know how recursion work inside a for loop

[Tim Cooke]

Have you run your code? What happens?

[Kasun Wixkramanayake]

3 2 1 2 1 3 2 1 2 1 3 2 1 2 1 (if call this method with value 3
) i get this out put.I don't know how it comes can you explain it me

[Paweł Baczyński]

I suggest getting paper and a pencil and writing this down.

When you execute x(3) it goes on stack.

So we have:

stack: x(3)
output:

x(3) prints " 3" and puts x(2) on stack (it's going to put it three times in total).

So we have:
stack: x(2) x(3)* (* means method that already started resolving and put one child on stack)
output: 3 (I'll skip spaces)

Ok so x(2) starts resolving. It prints " 2" and puts x(1) on stack (it's going to put it two times in total).
stack: x(1) x(2)* x(3)*
output: 3 2

Ok, so x(1) starts resolving. It prints " 1" and puts x(0) on stack (it's going to put it one time in total).
stack: x(0) x(1)* x(2)* x(3)*
output: 3 2 1

Ok, so x(0) starts resolving. It does nothing. x(0) completes.
stack: x(1)* x(2)* x(3)*
output: 3 2 1

Mehod x(1) should have executed x(0) one time. It have done this so it terminates.
stack: x(2)* x(3)*
output: 3 2 1

The execution goes back to x(2). It prints " 2" and puts x(1) on stack.

stack: x(1) x(2)** x(3)*
output: 3 2 1 2

And so on, and so on...

[Joe San]

To visualize it very simply, let us assume that you have methods 1 to 10 (method1, method2.... method10) wherein method1 calls method2, method2 calls method3 and so on until method10. All the method calls are places on the stack memory space allocated to the JVM. So the stack would be like:

method1
method2
method3
method4
method5
.......
.......
.......
method10

What you have to understand is that, to calculate the value for method1, method2 has to be first evaluated and to calculate method2, method3 has to be evaluated. So effectively, method10 has to be first evaluated. Now comparing this to your recursive function, the innermost loop which is satisfied until your i is less than n, that method returns a value (in your case nothing as you are just printing the value of n) and then the next method up in the stack gets evaluated until it reaches the top of the stack which is method1 in our analogy!

[Tim Cooke]

I second Pawel's recommendation. Also you might benefit from throwing a bunch of Sysout's into your code to help you follow the execution order. For example

    private static void x(int n) {
        System.out.println("Enter x(" + n + ")");
        for (int i = 0; i < n; i++) {
            System.out.println("Enter for loop. i = " + i + ", n = " + n);
            System.out.println("Before recursive call");
            x(n - 1);
            System.out.println("After recursive call");
        }
        System.out.println("Exit x(" + n + ")");
    }

For a call to x(3) results in

Enter x(3)
Enter for loop. i = 0, n = 3
Before recursive call
Enter x(2)
Enter for loop. i = 0, n = 2
Before recursive call
Enter x(1)
Enter for loop. i = 0, n = 1
Before recursive call
Enter x(0)
Exit x(0)
After recursive call
Exit x(1)
After recursive call
Enter for loop. i = 1, n = 2
Before recursive call
Enter x(1)
Enter for loop. i = 0, n = 1
Before recursive call
Enter x(0)
Exit x(0)
After recursive call
Exit x(1)

.... and so on .....


Nothing but some careful study and a bit of brain crunching it going to help you understand it.

[Kasun Wixkramanayake]

hey joe i am not good in English can you explain it little bit more

[Kasun Wixkramanayake]

hey joe i am not good in English can you explain it little bit more

So effectively, method10 has to be first evaluated. Now comparing this to your recursive function, the innermost loop which is satisfied until your i is less than n, that method returns a value (in your case nothing as you are just printing the value of n) and then the next method up in the stack gets evaluated until it reaches the top of the stack which is method1 in our analogy!

[Paweł Baczyński]

Have you tried to write down what the method does on paper?
I even started it for you...

[Kasun Wixkramanayake]

.i could not understand how this works on stack.it very confusing to me.

[Paweł Baczyński]

Read more about casll stack here: Call stack
Brief explanation here

[Kasun Wixkramanayake]

Pawel Pawlowicz thank you.Can you explain little bit more what you mean by *

[Scott Winterbourne]

Pawel Pawlowicz wrote:
So we have:
stack: x(2) x(3)* (* means method that already started resolving and put one child on stack)
output: 3 (I'll skip spaces)

He explains the meaning of * here in his previous post.

[Kasun Wixkramanayake]

Pawel Pawlowicz i follow your steps i can understand it but i have no idea how to write the rest of it.Please can you help me

[Paweł Baczyński]

Kasun Wixkramanayake wrote:Pawel Pawlowicz i follow your steps i can understand it but i have no idea how to write the rest of it.Please can you help me

Two parts of your sentence I highlighted are contradictionary. If you understood you coult write the rest. What part needs an explanation?

[Kasun Wixkramanayake]

x(1)x(2)****x(3)*

Am i correct

[Paweł Baczyński]

No, x(2)**** would suggest x(2) executed x(1) four times. It shouldn't do that.

When you see x(n) on the top of the stack check the number of asterisks.
- if the number of asterisks is equal to n, take x(n) out of the stack. That means that x(n) finished executing.
- if the number of asterisks is less that n, print n, add an asterisk and then put x(n-1) on the stack.
- if the number of asterisks is greater that n, then... you did something wrong. It shouldn't have more asterisks than n. Call to x(n) executes x(n-1) exactly n times.

Repeat the process until the stack is empty.

Important thing with stack. Well, you should know it already. You can only put an element on the top of the stack or remove an element from the top of the stack. No other operation is allowed.
Well... you could peek an element (see what it is) from the top of the stack but this is an equivalent of removing the element, seeing that it is and putting it back again.

Important note: the asterisk notation is something I invended for this example to keep track how many times one method executed another. You should not try to use it on other examples in exactly the same way.