We begin with a classic puzzle, the Towers of Hanoi (Figure 9-1)

The Towers of Hanoi |
---|

Players: 1 |

Object: To move a stack of disks from one of three pegs to a specified destination peg. |

Setup: There are three pegs. The first peg contains a number of disks, each smaller than the one beneath it. The other two pegs are initially empty. |

Play: On a turn, you can move the topmost disk from one peg to any other peg, with the restriction that a disk can never be on top of a smaller disk. |

As an example, the sequence of moves necessary to solve the three-disk version of the puzzle is shown in Figure 9-2.

Figure 9-2. There are seven moves in the solution to the three-disk Towers of Hanoi puzzle.

We want to write a program to solve the puzzle. Specifically, it should print out the sequence of moves needed to get all of the disks onto the destination peg. To move three disks from peg 1 to peg 3 (using peg 2 as a spare), our program should print:

1 => 3 1 => 2 3 => 2 1 => 3 2 => 1 2 => 3 1 => 3

Solving the one-disk puzzle is trivial: just move the disk directly from the source peg to the destination peg. We write a simple method (Figure 9-3), which we invoke as `hanoi1(1, 3)`.

Figure 9-3. A method to solve the one-disk Towers of Hanoi puzzle.

1 /** Move a single disk from source to dest. */ 2 public static void hanoi1(int source, int dest) { 3 System.out.println(source + " => " + dest); 4 } |

To solve the puzzle for two disks, we have to move the small disk to the spare peg to get it out of the way. We can then move the large disk to the destination, and then finally move the small disk back on top of it (Figure 9-4). We need to specify the spare disk as a third argument, so this method is invoked as `hanoi2(1, 3, 2)`.

Figure 9-4. The method for the two-disk puzzle requires an extra argument to identify the spare peg.

1 /** Move two disks from source to dest, using a spare peg. */ 2 public static void hanoi2(int source, int dest, int spare) { 3 System.out.println(source + " => " + spare); 4 System.out.println(source + " => " + dest); 5 System.out.println(spare + " => " + dest); 6 } |

The method for the three-disk puzzle (Figure 9-5) is somewhat longer.

The spacing in Figure 9-5 is there to suggest a key insight. The solution can be broken down into three parts. In lines 46, we move two disks from the source to the spare. In line 8, we move the largest disk from the source to the destination. In lines 1012, we move two disks from the spare to the destination.

Figure 9-5. The method `hanoi3()` is longer, but a pattern begins to emerge.

1 /** Move three disks from source to dest, using a spare peg. */ 2 public static void hanoi3(int source, int dest, int spare) { 3 4 System.out.println(source + " => " + dest); 5 System.out.println(source + " => " + spare); 6 System.out.println(dest + " => " + spare); 7 8 System.out.println(source + " => " + dest); 9 10 System.out.println(spare + " => " + source); 11 System.out.println(spare + " => " + dest); 12 System.out.println(source + " => " + dest); 13 14 } |

In lines 46, we are moving the two smallest disks. The location of the larger disk is irrelevant to this task. It is as if we were simply moving the two disks by themselves, and we already know how to do this. We can do this by invoking `hanoi2()`. The same is true of lines 1012. We can therefore write a shorter version of `hanoi3()` (Figure 9-6).

Figure 9-6. An improved version of `hanoi3()` invokes `hanoi2()`. Line 3 moves two disks from `source` to `spare`. Line 5 moves two disks from `spare` to `dest`.

1 /** Move three disks from source to dest, using a spare peg. */ 2 public static void hanoi3(int source, int dest, int spare) { 3 hanoi2(source, spare, dest); 4 System.out.println(source + " => " + dest); 5 hanoi2(spare, dest, source); 6 } |

Similarly, we can rewrite `hanoi2()` using `hanoi1()` (Figure 9-7).

Figure 9-7. The method `hanoi2()` can be rewritten using `hanoi1()`.

1 /** Move two disks from source to dest, using a spare peg. */ 2 public static void hanoi2(int source, int dest, int spare) { 3 hanoi1(source, spare); 4 System.out.println(source + " => " + dest); 5 hanoi1(spare, dest); 6 } |

We now have a pattern that will allow us to write a method to solve the puzzle for any number of disks, provided that we've written all of the previous methods. For example, once we've written `hanoi1()` tHRough `hanoi16()`, we can write `hanoi17()` (Figure 9-8).

Figure 9-8. The pattern can be extended to any number of disks.

1 /** Move 17 disks from source to dest, making use of a spare peg. */ 2 public static void hanoi17(int source, int dest, int spare) { 3 hanoi16(source, spare, dest); 4 System.out.println(source + " => " + dest); 5 hanoi16(spare, dest, source); 6 } |

This is fine, but we still have to do the tedious work of writing all these methods. It would be much better if we could write a single method which would work for any number of disks. This method has to accept the number of disks as an argument. A first attempt is shown in Figure 9-9. A method which invokes itself like this is called recursive.

Figure 9-9. First attempt at a method to solve the puzzle for any number of disks.

1 /** 2 * Move the specified number of disks from source to dest, making 3 * use of a spare peg. 4 */ 5 public static void hanoi(int disks, int source, int dest, 6 int spare) { 7 hanoi(disks - 1, source, spare, dest); 8 System.out.println(source + " => " + dest); 9 hanoi(disks - 1, spare, dest, source); 10 } |

Unfortunately, this method is slightly broken. If we ask for

hanoi(1, 1, 3, 2);

the program crashes, giving an error message like:

java.lang.StackOverflowError

We'll explain this message in more detail in Section 9.5. For now, let's step through the execution and see if we can figure out what happened.

The method begins by invoking

hanoi(0, 1, 2, 3);

which invokes

hanoi(-1, 1, 3, 2);

which invokes

hanoi(-2, 1, 2, 3);

and so on, until the computer runs out of memory. To prevent this, we have to provide a base casethat is, some situation where the problem is so simple that the method does not have to recursively invoke itself. For the Towers of Hanoi puzzle, the base case is the situation where there is only one disk. Once we check for the base case (Figure 9-10), our method works correctly.

Figure 9-10. A correct recursive program must check for the base case.

1 /** 2 * Move the specified number of disks from source to dest, making 3 * use of a spare peg. 4 */ 5 public static void hanoi(int disks, int source, int dest, 6 int spare) { 7 if (disks == 1) { 8 System.out.println(source + " => " + dest); 9 } else { 10 hanoi(disks - 1, source, spare, dest); 11 System.out.println(source + " => " + dest); 12 hanoi(disks - 1, spare, dest, source); 13 } 14 } |

In general, to solve a problem recursively, we must deal with two cases:

- The base case, where we can solve the problem directly, and
- The recursive case, where we solve the problem in terms of easier subproblems.

When we say that subproblems must be "easier," we mean that they must be closer to the base case. In the Towers of Hanoi, we solve the problem of moving n disks in terms of the easier problem of moving n 1 disks.

For a second example of recursion, consider the task of printing a LinkedList backward. An iterative approach (that is, one using loops instead of recursion) would be to find the last item, then the second-to-last item, and so on (Figure 9-11).

Figure 9-11. An iterative `toStringReversed()` method for our LinkedList class.

1 /** Return a String representing this list in reverse order. */ 2 public String toStringReversed() { 3 String result = "( "; 4 for (int i = size() - 1; i >= 0; i--) { 5 result += get(i) + " "; 6 } 7 return result + ")"; 8 } |

This method works, but it is not very efficient. Each invocation of `get()` requires us to walk down the list from the beginning to find the item at position `i`, which takes time linear in `i`. The total time for this version of `toStringReversed()` is:

(We are pretending here that String concatenation takes constant time, which is not exactly true. More on this in Chapter 13.)

A better recursive solution is to divide the problem into two cases:

- If there are no nodes, return the empty String.
- Otherwise, generate a String for the rest of the list (the part after the first item). Add the first item to the end of this String and return it.

We would like to add parentheses at the beginning and end of the list. We could deal with the left parenthesis in the base case, but there's no good time to add the right parenthesis. To avoid this complication, we move the recursive part of the problem into a separate helper method (Figure 9-12).

Figure 9-12. An alternate version of `toStringReversed()` invokes a recursive helper method.

1 /** Return a String representing this list in reverse order. */ 2 public String toStringReversed() { 3 return "( " + toStringReversedHelper(front) + ")"; 4 } 5 6 /** 7 * Return a String representing the portion of a LinkedList starting 8 * at node, in reverse order. 9 */ 10 protected String toStringReversedHelper(ListNode node) { 11 if (node == null) { 12 return ""; 13 } else { 14 return toStringReversedHelper(node.getNext()) + node.getItem() 15 + " "; 16 } 17 } |

Notice that `toStringReversedHelper()` does not deal with the entire list, but merely the chain of nodes starting at `node`.

To show that a recursive algorithm works correctly, we must demonstrate that:

- The base case works correctly, and
- If the recursive method works for a problem of size n 1, then it works for a problem of size n.

In this case, `toStringReversedHelper()` certainly works correctly for the base case, where `node` is `null`. It returns the empty String, so `toStringReversed()` returns `"( )"`.

Now suppose `node` is not `null`, but instead is a reference to the first of a chain of n nodes (Figure 9-13).

Figure 9-13. A chain of n nodes consists of a first node followed by n 1 more nodes.

If we assume that the recursive invocation

toStringReversedHelper(node.getNext())

correctly returns the String `"D C B "`, then clearly the expression

toStringReversedHelper(node.getNext()) + node.getItem() + " "

evaluates to `"D C B A "`, which is what we want. In general, if the method works for a chain of n 1 nodes, it works for a chain of n nodes.

Since we know that the method works properly for an empty chain (`null`), we can now conclude that it works for a chain of one node. From this, we can conclude that it works for a chain of two nodes. Indeed, we can conclude that it works for any number of nodes.

Let's write `toStringReversed()` for our ArrayList class as a third and final example of recursion. It would be easyand indeed, more naturalto do this one using a `for` loop, but it can also be done using recursion. In fact, any recursive procedure can be written iteratively, and vice versa.

Again we need a helper method, and the design of the algorithm is similar:

- If there are no elements being considered, return the empty String.
- Otherwise, generate a String for all of the elements after the current one. Add the current element to the end of this String and return it.

The code is shown in Figure 9-14, emphasizing the parts which are different from the LinkedList versions.

Figure 9-14. The method `toStringReversed()` and the recursive method `toStringReversedHelper()` for our ArrayList class.

1 /** Return a String representing this List in reverse order. */ 2 public String toStringReversed() { 3 return "( " + toStringReversedHelper(0) + ")"; 4 } 5 6 /** 7 * Return a String representing the portion of this List starting 8 * at position i, in reverse order. 9 */ 10 protected String toStringReversedHelper(int i) { 11 if (i == size) { 12 return ""; 13 } else { 14 return toStringReversedHelper(i + 1) + data[i] + " "; 15 } 16 } |

Exercises

9.1 |
Write a recursive method to compute n! (n factorial). |

9.2 |
Write a recursive method to compute the sum of the first n positive integers. |

9.3 |
Write a recursive method to determine whether a String is a palindromethat is, reads the same forward and backward. The Strings |

9.4 |
Write a recursive version of |

Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

- Inheritance
- Extending a Class
- The Object Class
- Packages and Access Levels
- Summary
- Vocabulary
- Problems
- Projects

Part II: Linear Structures

Stacks and Queues

- Stacks and Queues
- The Stack Interface
- The Call Stack
- Exceptions
- The Queue Interface
- Summary
- Vocabulary
- Problems
- Projects

Array-Based Structures

- Array-Based Structures
- Shrinking and Stretching Arrays
- Implementing Stacks and Queues
- The List Interface
- Iterators
- The Java Collections Framework: A First Look
- Summary
- Vocabulary
- Problems
- Projects

Linked Structures

- Linked Structures
- List Nodes
- Stacks and Queues
- The LinkedList Class
- The Java Collections Framework Revisited
- Summary
- Vocabulary
- Problems
- Projects

Part III: Algorithms

Analysis of Algorithms

- Analysis of Algorithms
- Timing
- Asymptotic Notation
- Counting Steps
- Best, Worst, and Average Case
- Amortized Analysis
- Summary
- Vocabulary
- Problems
- Projects

Searching and Sorting

- Searching and Sorting
- Linear Search
- Binary Search
- Insertion Sort
- The Comparable Interface
- Sorting Linked Lists
- Summary
- Vocabulary
- Problems
- Projects

Recursion

- Recursion
- Thinking Recursively
- Analyzing Recursive Algorithms
- Merge Sort
- Quicksort
- Avoiding Recursion
- Summary
- Vocabulary
- Problems
- Projects

Part IV: Trees and Sets

Trees

Sets

- Sets
- The Set Interface
- Ordered Lists
- Binary Search Trees
- Hash Tables
- The Java Collections Framework Again
- Summary
- Vocabulary
- Problems
- Projects

Part V: Advanced Topics

Advanced Linear Structures

- Advanced Linear Structures
- Bit Vectors
- Sparse Arrays
- Contiguous Representation of Multidimensional Arrays
- Advanced Searching and Sorting
- Summary
- Vocabulary
- Problems
- Projects

Strings

Advanced Trees

- Advanced Trees
- Heaps
- Disjoint Set Clusters
- Digital Search Trees
- Red-Black Trees
- Summary
- Vocabulary
- Problems
- Projects

Graphs

- Graphs
- Terminology
- Representation
- Graph Traversal
- Topological Sorting
- Shortest Paths
- Minimum Spanning Trees
- Summary
- Vocabulary
- Problems
- Projects

Memory Management

Out to the Disk

- Out to the Disk
- Interacting with Files
- Compression
- External Sorting
- B-Trees
- Summary
- Vocabulary
- Problems
- Projects

Part VI: Appendices

A. Review of Java

- A. Review of Java
- A.1. The First Program
- A.2. Variables and Types
- A.3. Loops
- A.4. Interacting with the User
- A.5. Branching
- A.6. Methods and Breaking Out
- A.7. Constants
- A.8. Operators
- A.9. Debugging
- A.10. Coding Conventions

B. Unified Modeling Language

C. Summation Formulae

- C. Summation Formulae
- C.1. Sum Notation
- C.2. Sum of Constants
- C.3. Sum of First n Integers
- C.4. Sums of Halves and Doubles
- C.5. Upper Limit on Sum of a Function
- C.6. Constant Factors

D. Further Reading

Index

Data Structures and Algorithms in Java

ISBN: 0131469142

EAN: 2147483647

EAN: 2147483647

Year: 2004

Pages: 216

Pages: 216

Authors: Peter Drake

Similar book on Amazon

Flylib.com © 2008-2020.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net