Python track: lab 2: fun with recursion

This lab involves recursion, which is the ability of a function to call itself.

The tower of hanoi problem

Description of the problem

This is a classic computer science problem which illustrates how recursion coupled with a divide-and-conquer strategy can enable you to trivially solve a problem which appears to be very difficult.

The set-up for the problem is as follows. You have three pegs, on which there are N disks of different sizes. The disks have sizes 1, 2, 3, ... N. All the disks start on the first peg, starting with disk N at the bottom and working consecutively up to disk 1. Your job is to move all the disks to the second peg. You can only move one disk at a time, and a disk can only be moved to an empty peg or to a peg whose top disk is larger than the disk being moved. Disks do not have to be placed on pegs in consecutive order i.e. it's OK to have disk 5 on top of disk 10 (but not on top of disk 4).

The algorithm to solve this problem goes like this. We'll call our pegs peg A, peg B, and peg C. Assume you want to move the top N disks from peg A to peg B.

  1. First, handle the base case i.e. the case that can be solved immediately. Here, the base case is when there is only one disk to move (N = 1). In that case, you just move the disk.

  2. If N > 1, the process is as follows:

    1. Move the top N-1 disks from peg A to peg C.
    2. Move disk N from peg A to peg B.
    3. Move the top N-1 disks from peg C to peg B.

    Note that steps 1 and 3 involve recursive calls to this algorithm. We call this the recursive case.

Both of these cases should be handled in the same function (method).

Amazingly enough, that's all there is to it. Recursive algorithms may seem like magic, but they can be understood by analogy with mathematical induction. With mathematical induction, you want to prove that something is true for all numbers N > 1. To do this, you prove that it's true for N = 0, and then you show that if it's known to be true for N-1, it can be proven to be true for N. Given that, you can show that it's true for any N > 0. Here, we see that we can move 1 disk (N = 1). If we know that we can move N-1 disks, then it's clear that we can move N disks (that's the recursive case).

Another useful thing to do is to take a small value of N (say 3) and work through the above algorithm on pencil and paper until you convince yourself that it does work.

The python program

Write your program in a single file called "" which will be called as follows:

    python <n>

where <n> is the number of disks that start on the first peg. If no number is supplied, the script should print out a usage message and exit as per the instructions in the python style guide.

Since this isn't a standalone script, don't include the

#! /usr/bin/env python

line at the top of the file, and don't make it executable either. This goes for all the upcoming labs as well.

Your program should define a class called Hanoi which encapsulates all the state variables of the problem. In particular, you should have an explicit representation of which disks are on which pegs at any given time. An easy way to do this is to have the pegs be python lists, and to have the disks be numbers that are stored in the lists in the correct order. Your Hanoi class should have the following methods:

You will probably want to define other methods as well (e.g. a helper method for solve() -- hint, hint).

In addition, you should print out the state of the problem (using your display method) before you start and after each move. The display should look exactly like this (for 8 disks):

    0:  4 1
    1:  8 7 6 5
    2:  3 2

where 0:, 1:, 2: identify the pegs and the other numbers identify the disks. Make sure that printouts for successive moves are separated by at least one blank line.

Your __init__ method should take the total number of disks as its only argument (other than self, of course) and check that this number is a positive integer. Raise a ValueError exception if it isn't, along with a meaningful error message.

Don't forget to read the style guide; in particular, we want you to use docstrings to document classes and functions. Also, don't forget to run your code through the python style checker before you submit it. Starting this week, we're going to be very picky about style violations.

For Extra Credit