(C++)

Finding the Maximum Recursively [Tail Method]

For this part of the lab activity, implement a recursive function that will find the maximum element in an array using the tail method discussed in lecture. This function should be generic, like the other versions from the lecture. Make sure to also conduct an asymptotic analysis for your implementation based on the number of comparison and arithmetic operations. Then, write some test cases in main to validate your implementation.

Tower of Hanoi

For the second part of the lab activity, implement a recursive function to solve the Tower of Hanoi problem. Use the following function prototype:

void towerHanoi(int, string, string, string, int&);

The first parameter is the number of disks. The second parameter is the source rod. The third parameter is the buffer rod. The fourth parameter is the target rod. The fifth parameter is the total number of moves made.

Your implementation should display a message when it "moves" a disk from the source rod to the target rod. It should be in the format:

Moving disc i from rod #x to rod #y

Make sure to also provide an asymptotic analysis based on the number of "moves".

Sample Run

The following is an example of what your program can display:

**************************************** Trying n = 1 Moving disc 1 from Rod #1 to Rod #3 Number of Moves = 1 **************************************** Trying n = 2 Moving disc 1 from Rod #1 to Rod #2 Moving disc 2 from Rod #1 to Rod #3 Moving disc 1 from Rod #2 to Rod #3 Number of Moves = 3 **************************************** Trying n = 3 Moving disc 1 from Rod #1 to Rod #3 Moving disc 2 from Rod #1 to Rod #2 Moving disc 1 from Rod #3 to Rod #2 Moving disc 3 from Rod #1 to Rod #3 Moving disc 1 from Rod #2 to Rod #1 Moving disc 2 from Rod #2 to Rod #3 Moving disc 1 from Rod #1 to Rod #3 Number of Moves = 7 **************************************** Trying n = 4 Moving disc 1 from Rod #1 to Rod #2 Moving disc 2 from Rod #1 to Rod #3 Moving disc 1 from Rod #2 to Rod #3 Moving disc 3 from Rod #1 to Rod #2 Moving disc 1 from Rod #3 to Rod #1 Moving disc 2 from Rod #3 to Rod #2 Moving disc 1 from Rod #1 to Rod #2 Moving disc 4 from Rod #1 to Rod #3 Moving disc 1 from Rod #2 to Rod #3 Moving disc 2 from Rod #2 to Rod #1 Moving disc 1 from Rod #3 to Rod #1 Moving disc 3 from Rod #2 to Rod #3 Moving disc 1 from Rod #1 to Rod #2 Moving disc 2 from Rod #1 to Rod #3 Moving disc 1 from Rod #2 to Rod #3 Number of Moves = 15