Thinking Recursively with Java

8.3. Exercises

8-1.	In the maze-solving program presented in this chapter, the program unmarks each square as it retreats while backtracking. Removing the marks from the blind alleys that the program tries along the way ensures that the final path will be displayed correctly. However, if the goal is to find the finish square in the shortest possible time, it is more efficient to leave these markers in place. Discuss how this change affects the efficiency of the algorithm. In what situations would this new approach improve the program's performance?
8-2.	Instead of awarding the game to the player who takes the last coin, Nim can also be played "in reverse" so that the player who takes the last coin loses. Redesign the strategy routines so that they give the correct moves for this "Reverse Nim" game, making as few changes to the existing code as you can.
8-3.	In the implementation of Nim used in the text, the simple case test included in isBadPosition is not strictly necessary, and the method could have been written more simply as private boolean isBadPosition(NimState state) { return findGoodMove(state) == null; } Why does this simplication work in this case?
8-4.	The algorithm presented in this chapter to solve the Nim game is quite inefficient because it must analyze the same position many different times. For example, if the computer plays first from the 3-4-5 position, making the first move requires 25,771 calls to isBadPosition. Since the total number of possible positions is only ...