Java Reference
In-Depth Information
FIGURE 14.3: Towers of Hanoi. Picture taken from Wikipedia Commons.
how a non-recursive solution can be developed. Our recursive code that solves the Tower of
Hanoi problem is shown next.
public class Test {
public static void main(String args []) {
move (8 , "needle 1" , "needle 3" , "needle 2" );
public static void move( int count , String sourceNeedle , String
destinationNeedle , String intermediateNeedle) {
if (count == 0) return ;
move(count 1, sourceNeedle , intermediateNeedle , destinationNeedle) ;
System. out . println ( "Move a ring from: " +sourceNeedle+ "to" +
destinationNeedle) ;
move(count 1, intermediateNeedle , destinationNeedle , sourceNeedle) ;
In the main method, we ask the move method to move 8 rings from Needle 1 to Needle 3.
This can be done by moving 7 rings from Needle 1 to Needle 2, 1 ring from Needle 1 to
Needle 3, and then 7 rings from Needle 2 to Needle 3. The seven rings are moved in the
same way using the same method. Note that, as expected, the move method starts with the
base case. If the variable count is equal to 0, then there are no rings to move and we are
14.3 Internal Details of a Recursive Call
In order to understand how recursion works, we first need to understand one of the most
primitive data structures: the stack . You can think of a stack as being a stack of dishes.
You have two operations: you can push a dish on top of the stack, or you can pop the dish
from the top of the stack. Only the top of the stack can be accessed.
For example, consider Figure 14.4. First, we push 3 on the stack. Then, we push the
number 5. At this point, only the top of the stack is accessible. If we execute the command
Search WWH ::

Custom Search