Python recursion – The Tower of Hanoi

I don’t have problem with recursion, but I did have problem with understanding the logic of the tower of Hanoi before. My husband even tried to explain the logic to me when he got a bad cold, but my brain was just like sticking in some place and couldn’t understand why.

But the logic is super simple when I finally figured it out.

If you don’t know how to play the tower of Hanoi, please visit here and play with it first, so you can understand the game rule of the tower of Hanoi.

hanoi_step1_03

There are only 3 steps, and we will use the graph of 3 disks to describe each step:

1) Move N-1 disks from the start pole to the intermediate pole

hanoi_step2_03

2) Move Nth disk from the start pole to the final pole

hanoi_step3_03

3) Move N-1 disks from the intermediate pole to the final pole

hanoi_step4_03

All you need to do is to use recursion to run those 3 steps for each disk because the simplest description of what your are doing in here is: Move N-1 disks to the empty pole, so you can move the N disk to the final pole; then put all N-1 disks back to the final pole.

That’s it!

If we use Python to implement this logic, it would be:


def hanoi(disk, start='START', end='END', middle='MIDDLE'):
    if disk > 0:
        hanoi(disk - 1, start, middle, end)
        print('Move disk %d from %s to %s' % (disk, start, end)) # Move the N disk
        hanoi(disk - 1, middle, end, start)

if __name__ == '__main__':
    hanoi(input('How many disks you wanna play? '))

It is pretty easy, isn’t it?

Related Articles:

Advertisements

3 thoughts on “Python recursion – The Tower of Hanoi

  1. Pingback: Go Recursion – The Tower Of Hanoi | Coding Air

  2. I know how to play the Tower of Hanoi but, It’s really difficult for me to understand your code even though it’s simple and easy to understand, oh well the problem is me,lol, can you please explain it to me?I really need it badly,thanks!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s