Thinking Recursively with Java

5.2. The Reductionistic View

One of the first things that new programmers learn is that computer programming requires a meticulous attitude with respect to details. When programming is involved, the statements "it's right except for a few details" and "it's wrong" are hard to differentiate experimentally. In a recursive implementation, those details are sometimes difficult to see, because the work consists primarily of keeping track of a list of active subproblems—details that the computer handles automatically.

To understand the underlying process behind that record keeping, it is useful to examine the execution history of a recursive program in complete detail. The Tower of Hanoi problem has two characteristics that make it particularly appropriate for this analysis. The problem is (1) hard enough that the solution is not obvious and (2) simple enough that you can follow the recursive logic without getting lost. With any luck, going through the details will dispel any lingering reductionistic tendencies and give you additional confidence in the recursive approach.

To simplify the basic problem, let's consider the necessary operations when only three disks are involved. In this case, the main program call is

moveTower(3, "A", "B", "C")

Now all you need to do is keep track of the operation of the program, particularly as it makes new calls to the moveTower procedure.

Following the logic of a recursive procedure is often tricky and may not be advisable for the fainthearted. The ...