|
|
|
|
|
|
|
int Factorial ( /* in */ int n )
{
if (n == 0)
return 1;
else
return n * Factorial(n - 1);
} |
|
|
|
|
|
|
|
|
The iterative version has two local variables, whereas the recursive version has none. There are usually fewer local variables in a recursive routine than in an iterative routine. Also, the iterative version always has a loop, while the recursive version always has a selection statementeither an If or a Switch. A branching structure is the main control structure in a recursive routine. A looping structure is the main control structure in an iterative routine. |
|
|
|
|
|
|
|
|
In the next section, we examine a more complicated problemone in which the recursive solution is not immediately apparent. |
|
|
|
|
|
|
|
|
One of your first toys may have been three pegs with colored circles of different diameters. If so, you probably spent countless hours moving the circles from one peg to another. If we put some constraints on how the circles or disks can be moved, we have an adult game called the Towers of Hanoi. When the game begins, all the circles are on the first peg in order by size, with the smallest on the top. The object of the game is to move the circles, one at a time, to the third peg. The catch is that a circle cannot be placed on top of one that is smaller in diameter. The middle peg can be used as an auxiliary peg, but it must be empty at the beginning and at the end of the game. |
|
|
|
|
|
|
|
|
To get a feel for how this might be done, let's look at some sketches of what the configuration must be at certain points if a solution is possible. We use four circles or disks. The beginning configuration is: |
|
|
|
|
|
|
|
|
To move the largest circle (circle 4) to peg 3, we must move the three smaller circles to peg 2. Then circle 4 can be moved into its final place: |
|
|
|
|
|
