• 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

recursion

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have understood the concept of recursion so far but this output gives me some trouble. I cant understand the output.
Here is the program



And here is the output

relocate slice 1 from A to C
relocate slice 2 from A to B
relocate slice 1 from C to B
relocate slice 3 from A to C
relocate slice 1 from B to A
relocate slice 2 from B to C
relocate slice 1 from A to C

Can anyone explain the output?
does it stay in this line until n is zero and then it execute the other lines?
Why is there at the beginning A and C as an output.
I am very glad if you can help me I really want to understand recursion.
Thanks a lot =)
 
Bartender
Posts: 2856
10
Firefox Browser Fedora Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi, welcome to Javaranch

Dung Ho wrote:does it stay in this line until n is zero and then it execute the other lines?
Why is there at the beginning A and C as an output.


Yes the line 4 from your code starts the recursion with n=2 and continues until n=1. Since that is the first line of the function, the start ='A' and goal ='C' passed originally with n=3 do not change until n becomes 0 which stops the recursion.
When the recursion stops, the print statement prints the n value which is 1, hence the output.
Similarly you can trace the remaining output.

Hope this helps
 
Amit Ghorpade
Bartender
Posts: 2856
10
Firefox Browser Fedora Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If this is your very first program on recursion, then I would suggest trying a simpler one like Factorial of a number or the Fibonacci series.
Also it will be easy to understand if you work out the recursion with a pen and paper by hand and then run the program to verify you got correct results.
Reverse engineering from a program output is not the best way to understand the concept for a new learner.

Just my 2 cents.
 
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Think of the calls to relocate() in a tree form, the output is in the following order Child->Parent->Child this means that the root of the tree doesn't produce output until it's left child has finished.
The function calls itself twice, which means each node has two children (except the leaves) and the depth of the tree is 3 since n is decremented by 1 each time.
This means that the depth is 3, number of children of each node (except the leaves) is 2 and the total number of nodes is 7. (hence the number of lines in output)
The first time relocate() is called it doesn't output anything until it's first child has finished (a true depth-first order tree would wait for all its children to finish), this is true for all nodes in the tree.
The tree looks like this

1. relocate(3,'A','B','C') -> "relocate slice 3 from A to C"
2. ->relocate(2,'A','C','B') -> "relocate slice 2 from A to B"
3. ->->relocate(1,'A','B','C') -> "relocate slice 1 from A to C"
4. ->->relocate(1,'C','A','B') -> "relocate slice 1 from C to B"
5. ->relocate(2,'B','A','C') -> "relocate slice 2 from B to C"
6. ->->relocate(1,'B','C','A') -> "relocate slice 1 from B to A"
7. ->->relocate(1,'A','B','C') -> "relocate slice 1 from A to C"

the -> denotes the depth in the tree, the order of the output is 3,2,4,1,6,5,7 (Child->Parent->Child)
 
reply
    Bookmark Topic Watch Topic
  • New Topic