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.
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
2) Move Nth disk from the start pole to the final pole
3) Move N-1 disks from the intermediate pole to the final pole
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.
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?