Objective
Gain an understanding of recursive algorithms through the implementation of a recursive algorithm (Tower of Hanoi)
Supports Learning Outcomes 3, 4
3. Implement data structures and algorithms in computer code.
4. Analyze the performance of algorithms and data structures.
Introduction
Recursion is the ability of a function to call itself recursively (definition). Recursion is quite easy and also quite practical. Just don’t forget to put in an exit clause to your recursive functions, or you will find yourself staring at a spinning hourglass while the algorithm chews up all your available resources.
Tower of Hanoi
The classic example of a recursive solution to a relatively complex problem is the Tower of Hanoi https://en.wikipedia.org/wiki/Tower_of_Hanoi – which is taught in every Computer Science program and in a lot of programming classes. As you add disks, the solution becomes more computationally complex, but the algorithm to solve it is a simple repetition of moves. I highly recommend you understand the tower and the recursive solution – this video will both amaze you and help you understand the problem – https://youtu.be/2SUvWfNJSsM
Assignment
Use the Stack you created from previous assignments (Assignment 5) for the Stack needed for this assignment,.
We are going to solve the classic Tower of Hanoi. Using the Wikipedia article, I want you to write a computer program that calculates the number of moves necessary to solve the Tower of Hanoi given a number of disks. There are formulas that calculate this – you are NOT going to use them. You will calculate this by implementing the recursive algorithm of the tower and counting every time a block is moved. You may also want to print out the moves. I recommend not allowing input greater than 7 blocks – it starts getting pretty big after that.
This can easily be implemented by using your Stack from previous assignments – all you really do in this is push and pop from the stack.
Answer the following questions in the interface of your code;
1. What is the Complexity (In Big O)?
2. Should we be concerned with the legend of the world ending when the 64 disk solution is physically solved if it takes 1 second for each move? Calculate many years it will take to complete the tower. (Put the answer to this and the complexity either in the submission or in the comments of the computer program)
The video at https://youtu.be/Qh8qmxb8Wps will be very useful.
Assignment Grading Criteria – I don’t need to actually see every move printed out (it may help you in coding the algorithm, though) – I do need to see it actually counting the moves, and it should give the correct number of moves for all cases. You can verify the count using the equation 2^n – 1.