Kim-Dung Ho

Greenhorn

Posts: 1

posted 4 years ago

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 =)

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 =)

posted 4 years ago

Hi, welcome to Javaranch

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

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

SCJP, SCWCD.

|Asking Good Questions|

posted 4 years ago

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.

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.

SCJP, SCWCD.

|Asking Good Questions|

Jón Jónsson

Greenhorn

Posts: 5

posted 4 years ago

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

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)

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)