Thinking Recursively with Java

5.3. Exercises

5-1.	In making a recursive subdivision of a problem, it is extremely important to ensure that any generated subproblems obey exactly the same rules as the original. With this caveat in mind, consider the following decomposition: If n is one, simply move that disk from start to finish. If n is greater than one, divide the problem up into three subgoals: Move the top disk from start to temp. Using a recursive call, move the remaining tower of n-1 disks from start to finish. Move the top disk back from temp to finish. Why does this algorithm fail?
5-2.	By following the logic of the moveTower function, write a Java function nHanoiMoves(n) that returns the number of moves required to solve the Tower of Hanoi puzzle for a tower of size n.
5-3.	In designing a recursive solution, it is usually wise to make the simple cases as simple as possible. For the Tower of Hanoi program, for example, the best choice may not be that of a single disk as described in the chapter. An even easier case occurs when a tower has no disks at all, in which case there is no work to do. Rewrite the implementation of moveTower so that it uses zero rather than one as its simple case.
5-4.	Using mathematical induction, prove that the number of moves required to transfer a tower of size n by the moveTower algorithm is 2 n − 1.