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.
Recursion is simply put the ability of a function to recursively call itself. 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.
In All Course Lectures recursion is covered in 3.2 (Recursive Algorithms).
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 complex, but it is a simple repetition of moves used in the 3 disk solution.
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 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. Also I recommend not allowing input greater that 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 concerned with the legend of the world ending when the 64 disk solution is physically solved it it takes 1 seconds for each move? How many years will it take to complete the tower?
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 which you can verify using the equation 2^n - 1.