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
done.
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