# 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 "`hanoi.py`" which will be called as follows:

```    python hanoi.py <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:

• `display`, which prints the current state of the problem (which disks are on which pegs).
• `solve`, which solves the problem. `solve` should take no arguments.
• `move`, which moves one disk from one peg to another. Use an `assert` statement to make sure you aren't doing an illegal operation (e.g. putting a disk on top of a smaller disk, or duplicating a disk).

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

• Add code to count the number of moves made when solving the problem. Print this number after you've finished solving the problem. How does this number vary with the number of disks?

• Add code to determine the maximum recursion depth reached while solving the problem and print it out. How does this number vary with the number of disks?

• Add a command-line option `-v` (for "verbose") which, if present, will print out the state of the problem after each move. If it's not present, the problem will be solved silently. Allow the `-v` option to be located anywhere on the command line (as long as it's after the `python hanoi.py` arguments, of course).