• Post Reply Bookmark Topic Watch Topic
  • New Topic

java recursion  RSS feed

 
Kasun Wixkramanayake
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


can you tell me how this recursion works.
 
Tim Cooke
Marshal
Posts: 4051
239
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
no i know how the recursion work but i don not know how recursion work inside a for loop
 
Tim Cooke
Marshal
Posts: 4051
239
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Have you run your code? What happens?
 
Kasun Wixkramanayake
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 2087
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 Harry
Ranch Hand
Posts: 10128
3
Eclipse IDE Mac PPC Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
 
Tim Cooke
Marshal
Posts: 4051
239
Clojure IntelliJ IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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

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
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hey joe i am not good in English can you explain it little bit more
 
Kasun Wixkramanayake
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 2087
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Have you tried to write down what the method does on paper?
I even started it for you...
 
Kasun Wixkramanayake
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
.i could not understand how this works on stack.it very confusing to me.
 
Paweł Baczyński
Bartender
Posts: 2087
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Read more about casll stack here: Call stack
Brief explanation here
 
Kasun Wixkramanayake
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Pawel Pawlowicz thank you.Can you explain little bit more what you mean by *
 
Scott Winterbourne
Ranch Hand
Posts: 116
2
Eclipse IDE Java PHP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 2087
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
x(1)x(2)****x(3)*

Am i correct
 
Paweł Baczyński
Bartender
Posts: 2087
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!