Watch as 5-disk Tower unfolds **here**.

When I saw the Towers of Hanoi project, I thought it would have something to do with solving the problem, but it turns out to be a module that allows the user to play the game, via (appropriately) the user-defined “stack” - based data structure. I added a “graphic” add-on, which you can find **here**, but the interesting stuff is in the solution.

When you study recursion, the examples always given are factorial, fibonacci, and palindromes, all problems that illustrate recursion, but which might generate a bit of “so what?” attitude, since they can all be easily coded iteratively. But the Towers of Hanoi problem provides a superb example of the beauty of recursion, since it provides in an amazingly few lines a solution that, in iterative form, is much more difficult.

I’m not going to go into the explanation, but there is a very nice one **here**, beginning at 20:20. I have taken the code from that lecture and changed only the order of the parameters to correspond with our “L”, “M” and “R”. I have also replaced the `printMove()`

line with one that actually does the move in our module - `to.push(fr.pop())`

- then prints out the graphic with a small (optional) delay.

So, to implement this, begin with the module, as modified via the above link to implement ASCII-graphics.

To the top of your module, add

```
import time
DELAY = 0.5 # delay in seconds
```

Now, comment out everything after #Play the Game

In its place, paste in the following code:

```
num_moves = {'n':0}
def towers(n, fr, spare, to):
if n == 1:
to.push(fr.pop())
time.sleep(DELAY)
print_pix()
num_moves['n'] += 1
else:
towers(n-1, fr, to, spare)
towers(1, fr, spare, to)
towers(n-1, spare, fr, to)
print_pix()
towers(num_disks, left_stack, middle_stack, right_stack)
num_user_moves = num_moves['n']
print("\n\nI completed the game in {0} moves, and the optimal number of moves is {1}".format(num_user_moves, num_optimal_moves))
```

Run it as usual. Of course, you can change the delay at the top of the module, 0 = no delay.