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:

To describe the state of the system at any given moment of time, let us use In each array x (= a, b, or c), In this case, initially, num_a = n, and num_b = num_c = 0, and 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:

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.