Overview / Logistics

The purpose of this lab is to get you practice with recursion, and to show you how recursion can be used to plan the solution to a very complex problem with many steps in just a few lines of code.

We talked about the Towers of Hanoi problem in the recursion module, and we came up with a way of computing the optimal number of steps, but now we're going to take it to the next level and actually show what the steps are in an animation.

Click here to download the starter code for this exercise. It represents each peg as a stack, which uses a singly-linked list at the underlying data structure (click here to see that code).

Your task: Fill in the solve_rec method in hanoi.py to recursively show a solution. Every time you move a peg, you should call self.draw_frame(), which will save an image of that step to the folder where you're running the code. As you go, you will have to change the role of pegs, so you'll have to carefully figure out which pegs to pass along as the "source," "target," and "free" pegs.

To see the progress of the solver, you can use the provided draw_frame method. Be sure to only call self.draw_frame() directly after you move a disc, and nowhere else.

Below are a few examples of this working. To run this, an object is initialized at the bottom

This will output a bunch of frames as png images of each step.

---

Hanoi(2)

Hanoi(3)

Hanoi(4)

Hanoi(5)

Hanoi(6)