2. Problem C-5.16 from textbook. You can use the following algorithm for this purpose (assuming that the pegs (i.e. rods) are labeled as a, b, and c, and the disks are on peg a and we want to move the disks from peg a to peg c using peg b as temporary storage). void Tower_of_Hanoi(int n, char from_peg, char to_peg, char temp_peg) if (n == 0) return; //base case Move n-1 disks from from_peg to temp_peg using to_peg as helper (i.e. temporary storage) by making a recursive call Move the last disk (nth disk) from from_peg to to_peg (implement this move as a print statement that moves the last disk to to_peg) Move n-1 disks from temp_peg to to_peg using from_peg as helper (i.e. temporary storage) by making a recursive call. Implement this algorithm using recursion and write a main method to test your method.

-5.16 In the Towers of Hanoi puzzle, we are given a platform with three pegs, a,b, and c, sticking out of it. On peg a is a stack of n disks, each larger than the next, so that the smallest is on the top and the largest is on the bottom. The puzzle is to move all the disks from peg a to peg c, moving one disk at a time, so that we never place a larger disk on top of a smaller one. See Figure 5.15 for an example of the case n=4. Describe a recursive algorithm for solving the Towers of Hanoi puzzle for arbitrary n. (Hint: Consider first the subproblem of moving all but the nth disk from peg a to another peg using the third as "temporary storage.") Figure 5.15: An illustration of the Towers of Hanoi puzzle