• Post Reply Bookmark Topic Watch Topic
  • New Topic

recursion  RSS feed

 
Kim-Dung Ho
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • 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 =)
 
Amit Ghorpade
Bartender
Posts: 2856
10
Fedora Firefox Browser Java
  • Mark post as helpful
  • send pies
  • 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
Fedora Firefox Browser Java
  • Mark post as helpful
  • send pies
  • 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.
 
Jón Jónsson
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • 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)
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!