[ Data Structures with Java ] Section 6.2 : Recursive Applications

Preface : 
Up to this point, our study of recursion has involved algorithms that have alternative iterative solutions that are simple to code. The examples illustrate the design and implementation of recursive algorithms. They do not, however, let you appreciate the true importance of recursion as an algorithm design strategy. One of the most powerful features of recursion is its ability to allow a programmer to solve problems that would be difficult to design and implement as an iterative process. In this section, we illustrate this feature with an algorithm to draw tic marks on a line. A more interesting example is the famous Tower of Hanoi puzzle, which has an elegant recursive solution. 

Building a Ruler : 
A typical ruler is a sequence of inch-long intervals with separator marks. Each inch has a shorter mark at the 1/2-inch point and progressively shorter marks at 1/4-inch intervals and so forth. The problem is to create a program that draws marks at regular intervals on a line. The sizes of the marks differ, depending on the specific interval. The recursive method drawRuler() provides the solution. Its algorithm assumes the existance of the methoddrawMark(), which takes a point x and an integer value h as arguments and draw a vertical line at point x withc size proportional to h. 
Let us trace the sequence of actions for the drawRuler() algorithm, assuming h is initially 3 and the interval is 1 inch, which low=0.0 and high=1.0. Each step draws a mark at the midpoint of an interval. Using the midpoint to separate the interval into half-lines, the step makes two recursive calls todrawRuler() to draw smaller marks at the midpoint of each half-line : 
 

The drawRuler() method takes the endpoints of an interval and the level h as arguments. The first action is to draw a mark at the midpoint and then make two recursive calls to draw the marks in the two half-intervals, below is the sample code : 

- 函式 drawRuler() 範例代碼 :

view plaincopy to clipboardprint?

1. public static void drawRuler(double low, double high, int h) {  
2.     if(h>0) {  
3.         double midPoint = (low+high)/2;  
4.         _drawMark(midPoint);  
5.         drawRuler(low, midPoint, h-1);  
6.         drawRuler(midPoint, high, h-1);  
7.     }  
8. }  
9.   
10. protected static void _drawMark(double point){  
11.     System.out.printf("Draw point(%.2g)\n", point);  
12. }  

Towers of Hanoi : 
Puzzle fans have long been fascinated with the Towers of Hanoi problem, which involves a stack of n graduated disks and a set of three needles called A, B, and C. The initial setup places the n disks on needle A. The task is to move the disks once at a time from needle to needle until the process rebuilds the original stack, but on needle C. In moving a disk, a larger disk may never be placed on top of a smaller disk. 
In general, the algorithm that moves n disks require 2^n-1 moves. At first glance, you might think that solving the Towers of Hanoi puzzle would be daunting in terms of both time and strategy. Somewhat surprisingly, perhaps, the Tower of Hanoi has a relative simple relatively simple recursive solution. We illustrate the algorithm by looking at the simple three-disk Hanoi puzzle. Watch the steps as we move disks from needle A to C by way of the intermediate needle B. For discussion purposes, we break up the moves into separate stages encompassing several steps. These stages will be used later to develop the recursive method hanoi() : 
 
 

As expected, n=3 so it takes 2^3-1=7 moves. To understand the recursive native of the process, note that Stage 1 and Stage 3 both describe separate Towers of Hanoi problems with two disks. In the first stage, two disks move from needle A to needle B, with needle C serving as temporary storage. In the third stage, two disks move from needle B to needle C, with needle A serving as temporary storage. The fact that the Towers of Hanoi algorithm involves a smaller version of the algorithm makes it recursive. The three-disk problem reduces to two two-disks problems. 

The Recursive Method hanoi() : 
The recursive process translates into the method called hanoi(). The arguments include n, the number of disks, and three string arguments that denote the name of the starting needle(initNeedle), the destination needle(endNeedle), and the intermediate needle(tempNeedle) that temporarily holds disks during the moves. The following is the method implementation : 

- hanoi() 函式範例代碼 :

view plaincopy to clipboardprint?

1. public static void hanoi(int n, String initNeedle, String endNeedle, String tempNeedle) {  
2.     if(n==1) {  
3.         System.out.printf("Move from %s to %s...\n", initNeedle, endNeedle);  
4.     } else if(n>1) {  
5.         hanoiBookVersion(n-1, initNeedle, tempNeedle, endNeedle);  
6.         hanoiBookVersion(1, initNeedle, endNeedle, tempNeedle);  
7.         hanoiBookVersion(n-1, tempNeedle, endNeedle, initNeedle);  
8.     }  
9. }  

Actually the hanoi() can be break into three steps. Considering n disks, the first step is to move n-1 disks from initNeedl to tempNeedle : 
hanoi(n-1, initNeedle, tempNeedle, endNeedle); // recursive call for stage1 

The second step is to move the largest disk from initNeedle to endNeedle : 
hanoi(1, initNeedle, endNeedle, tempNeedle); // Here use n=1 because we only take the largest disk into account 

The last step, of course, is to move the last disks(n-1) from tempNeedle to endNeedle : 
hanoi(n-1, tempNeedle, endNeedle, initNeedle); // Complete the n-disks hanoi problem.