• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

java recursion

 
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


can you tell me how this recursion works.
 
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Have you run your code? What happens?
 
Kasun Wixkramanayake
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Bartender
Posts: 2236
63
IntelliJ IDE Firefox Browser Spring Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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...
 
Ranch Hand
Posts: 10198
3
Mac PPC Eclipse IDE Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 2236
63
IntelliJ IDE Firefox Browser Spring Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
.i could not understand how this works on stack.it very confusing to me.
 
Paweł Baczyński
Bartender
Posts: 2236
63
IntelliJ IDE Firefox Browser Spring Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Pawel Pawlowicz thank you.Can you explain little bit more what you mean by *
 
Ranch Hand
Posts: 116
2
Eclipse IDE PHP Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 2236
63
IntelliJ IDE Firefox Browser Spring Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
x(1)x(2)****x(3)*

Am i correct
 
Paweł Baczyński
Bartender
Posts: 2236
63
IntelliJ IDE Firefox Browser Spring Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic