## CS 2401 Assignment #3

Due Date: Monday, September 27 or Tuesday, September 28, depending on the day of your lab.

Objective: The goal of this assignment is to practice recursion.

Assignment: One of the examples of recursion described by our textbook is Hanoi tower. Write a program that, given the number n of disks, solves the corresponding Hanoi tower problem, and shows, step by step, how the configuration of disks will change in the process of solution.

Use recursion to create a list of disk motions that solve the Hanoi tower problem, then follow this list and trace how the disks will actually be moved. For that, you will need to keep track of the configuration at each moment of time, describe how the configuration will change with every move, and visualize each configuration. Use a special method to visualize a configuration.

To describe a configuration, let us number the original disks:

• 1 will indicate the top (smallest) disk,
• 2 will indicate the next to top disk,
• ...,
• n will indicate the largest (bottom) disk.
To describe the state of the system at any given moment of time, let us use
• three integer arrays a[], b[], and c[] of size n describing which disks are placed on each pole, and
• three integers num_a, num_b, and num_c indicating how many disks are currently located on each pole.
In each array x (= a, b, or c),
• the value x[0] described which disk is at the bottom,
• the value x[1] describes which which disk is at the next-to-bottom location,
• etc.
In this case, initially, num_a = n, and num_b = num_c = 0, and
• a[0] = n (the largest disk is at the bottom),
• a[1] = n-1,
• ...,
• a[n - 1] = 1 (the smallest disk is at the top).
In general, the top disk at location A is a[num_a - 1], the top disk at location B is b[num_b - 1], and the top disk at location C is c[num_c - 1].

Feel free to use the simplest possible drawings. For example, for n = 2, the initial configuration can be represented as follows:

```Previous step: none

|          |          |
|          |          |
X|X         |          |
XX|XX        |          |
-------    -------    --------
A          B          C
```
In this configuration, num_a = 2, num_b = num_c = 0, a[0] = 2, and a[1] = 1.

When me move the top disk from A to C, we decrease the number of disks num_a at the pole A by 1, and increase the number of disks num_c at the pole C by 1. The new value c[num_c - 1] describing which disk is now at the top of the pole C can be determined from the fact that this disk was originally at the top of pole A. So:

• we increase num_c by 1, creating a place for the new disk;
• we describe disk is placed at the new location c[num_c - 1], by assigning to the variable c[num_c - 1], a new value a[num_a - 1] -- the value describing the disk which was originally at the top of pole A;
• after that, we decrease num_a by 1, indicating that there is no one fewer disk at pole A.
In the above example, after moving the top disk from pole A to pole C, we get the following configuration:
```Previous step: A --> C

|          |          |
|          |          |
|          |          |
XX|XX        |         X|X
-------    -------    --------
A          B          C
```
In this new configuration, num_a = 1, num_b = 0, num_c = 1, a[0] = 2, and c[0] = 1.