Kasun Wixkramanayake

Ranch Hand

Posts: 74

posted 3 years ago

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?

If not, then exactly what are you asking?

Tim Driven Development

Kasun Wixkramanayake

Ranch Hand

Posts: 74

Kasun Wixkramanayake

Ranch Hand

Posts: 74

posted 3 years ago

- 1

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...

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...

posted 3 years ago

- 1

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:

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!

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!

SCJP 1.4, SCWCD 1.4 - Hints for you, Certified Scrum Master

Did a rm -R / to find out that I lost my entire Linux installation!

posted 3 years ago

- 1

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

For a call to x(3) results in

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

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 .....

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.

Tim Driven Development

Kasun Wixkramanayake

Ranch Hand

Posts: 74

Kasun Wixkramanayake

Ranch Hand

Posts: 74

posted 3 years ago

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!

Kasun Wixkramanayake

Ranch Hand

Posts: 74

Kasun Wixkramanayake

Ranch Hand

Posts: 74

Kasun Wixkramanayake

Ranch Hand

Posts: 74

posted 3 years ago

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

Kasun Wixkramanayake wrote:Pawel Pawlowicz i follow your stepsi can understand itbuti have no idea how to write the restof 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?

posted 3 years ago

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

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.