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:
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 CIn this configuration, num_a = 2, num_b = num_c = 0, a = 2, and a = 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:
Previous step: A --> C | | | | | | | | | XX|XX | X|X ------- ------- -------- A B CIn this new configuration, num_a = 1, num_b = 0, num_c = 1, a = 2, and c = 1.