Page 826 - Introduction to Programming with Java: A Problem Solving Approach

792 Appendix 8 Recursion
/*************************************************************
*
Towers.java
Dean & Dean
This uses a recursive algorithm for Towers of Hanoi problem.
*************************************************************/
*
*
*
public class Towers
{
public static void main(String[] args)
{
}
move(4, 'A', 'C', 'B');
// Move n disks from source s to destination d using temporary t.
private static void move(int n, char s, char d, char t)
{
System.out.printf(
"call n=%d, s=%s, d=%s, t=%s\n", n, s, d, t);
if (n == 1)
{
// recursive stopping condition
System.out.printf("move %d from %s to %s\n", n, s, d);
}
else Apago PDF Enhancer {
move(n-1, s, t, d); // source to temporary
System.out.printf("move %d from %s to %s\n", n, s, d);
move(n-1, t, d, s); // temporary to destination
}
// end class Towers
}
}
System.out.println("return n=" + n);
two return points
Figure A8.8 Solution to Towers of Hanoi problem
Shaded statements are for diagnostic tracing. Remove them for final implementation.
Figure A8.9 displays the output. The shaded lines are lines printed by the shaded print statements in Figure A8.8. As we said, they are just to help you see what happened and are not part of the solution. The solution is given by the un-shaded outputs. The most difficult part of tracing a recursive algorithm like this is keeping track of the place from which a call was made and therefore where execution resumes after a return. As our note in Figure A8.8 indicates, sometimes the call is made from the “source to temporary” statement, and sometimes the call is made from the “temporary to destination” statement. Fortunately, if you define a recursive algorithm correctly, you can ignore the details of how it plays out during program execution.
We recommend that you cut out four little paper disks of different sizes, number them 1 through 4 from smallest to largest, and build a tower at location “A” on your left. Then move the disks one at a time as the un-shaded outputs in Figure A8.9 say. You’ll see that the tower does in fact get moved from location “A” to location “C” in precise conformity with the specified rules. This works because the eventual moves are informed by goal information in earlier method calls.