Question

On the handout for the Lecture 8, we have a recursive algorithm for the problem of the Towers of Hanoi.

If I run that algorithm in the following way: Towers(3,1,2,3) I get this results:

Move disk from 1 to 2
Move disk from 1 to 3
Move disk from 2 to 3
Move disk from 1 to 2
Move disk from 3 to 1
Move disk from 3 to 2
Move disk from 1 to 2

But if I try to "run that piece of code in my head the order of results is the following:

1,2
/ \
1,3 3,2
/ \ / \
1,2 2,3 3,1 1,2

Could someone, please, explaine to me what the program fl

Answer 1

My question appears broken, my initial question was whether someone could, please, tell me what the program flow is so I can understand the logic for which the different disk movements appear on screen.

As running this algorithm in my head, it seems like the answers should come in this way: 1,2 / 1,3 / 3,2 / 1,2 / 2,3 / 3,1 / 1,2

Thank you in advance.

Answer 2

http://dpaste.com/596485/
play around with print statements til it makes sense
doing recursive algorithms in your head can get you all tied up in knots

Answer 3

Thank you!

Contrary to the course, I'm using Python v3.x so I had to slightly adapt your code: http://dpaste.com/596533/

I've got this printout after running the program Towers2(3,1,2,3):

>>> Towers2(3,1,2,3)
********* new instance ************
a
Move disk from 1 to 2
Move disk from 1 to 3
Move disk from 2 to 3
b
Move disk from 1 to 2
c
Move disk from 3 to 1
Move disk from 3 to 2
Move disk from 1 to 2
going back up the recursion path

Why does it print "new instance" and "going back up the recursion path" only once?

Answer 4

you changed the function name but didn't make the change in line 7, 9, and 11

Answer 5

Much to my shame, you're right. Thank you! :)