This section presents two more case studies in recursion: Tower of Hanoi and picture processing with recursion.
The Towers of Hanoi problem is a representation of an old Asian puzzle. It involves moving a specified number of disks from one tower (or peg) to another. The disks are arranged on the first tower in order of increasing size, with the largest disk on the bottom. Legend has it that the world will come to an end when the problem is solved for 64 disks. In the version of the problem shown in Figure 13.5 there are five disks (numbered 1 through 5) and three towers or pegs (lettered A, B, C). The goal is to move the five disks from peg A to peg C subject to the following rules:
Figure 13.5
PROBLEM SPECIFICATION
Solve the Towers of Hanoi Problem for N disks, where N is a parameter.
ANALYSIS
The solution to the Towers of Hanoi problem consists of a printed list of individual disk moves. We need a recursive procedure that can be used to move any number of disks from one peg to another, using the third peg as an auxiliary.
Data Requirements
Problem Inputs
the number of disks to be moved (N : Integer)
the from peg (FromPeg : 'A'..'C')
the to peg (ToPeg : 'A'..'C')
the auxiliary peg (AuxPeg : 'A'..'C')
Problem Outputs
a list of individual disk moves
DESIGN
The stopping cases of the problem involve moving one disk only (e.g., "move disk 2 from peg A to peg C"). A simpler problem than the original would be to move four disks subject to the conditions above, or three disks, and so on. Therefore, we want to split the original five-disk problem into one or more problems involving fewer disks. Let's consider splitting the original problem into the three problems below.
Figure 13.6
Unfortunately, we still don't know how to perform step 1 or step 3. However, both these steps involve four disks instead of five so they are simpler than the original problem. We should be able to split them into even simpler problems. Step 3 involves moving four disks from tower B to tower C, so we can split it into two three-disk problems and a one-disk problem:
3.1. Move three disks from peg B to peg A.
3.2. Move disk 4 from peg B to peg C.
3.3. Move three disks from peg A to peg C.
Figure 13.7 shows the status of the towers after completing steps 3.1 and 3.2. We now have the two largest disks on peg C. Once we complete step 3.3, all five disks will be on peg C as required.
Figure 13.7
By splitting each N-disk problem into two problems involving N - 1 disks and a one-disk problem, we will eventually reach all cases of one disk, which we know how to solve.
INITIAL ALGORITHM
1. IF N is 1, THEN
2. Move disk 1 from the from peg to the to peg
ELSE
3. Move N-1 disks from the from peg to the
auxiliary peg using the to peg
4. Move disk N from the from peg to the to peg
5. Move N-1 disks from the auxiliary peg to the
to peg using the from peg
END IF;
If N is 1, a stopping case is reached. If
N is greater than 1, the recursive step (following
ELSE) splits the original problem into three smaller subproblems,
one of which is a stopping case. Each stopping case displays a move
instruction. Verify that the recursive step generates the three problems listed
after
Figure
13.5 when N is 5, the from peg is
A, and the to peg is C.
IMPLEMENTATION
The implementation of this algorithm is shown as procedure Tower in
Program
13.9. Procedure Tower has four parameters. The procedure call
statement
Tower ( N => 5, FromPeg => 'A',ToPeg => 'C',AuxPeg => 'B');
solves
the problem posed earlier of moving five disks from tower A to
tower C using B as an auxiliary. An auxiliary
procedure MoveDisk is included.
Program 13.9
WITH Ada.Text_IO;
WITH Ada.Integer_Text_IO;
PROCEDURE Test_Tower IS
------------------------------------------------------------------------
--| Demonstration of the recursive procedure Tower,
--| which solves a 3-peg Towers of Hanoi problem
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: July 1995
------------------------------------------------------------------------
SUBTYPE Pegs IS Character RANGE 'A'..'C';
PROCEDURE MoveDisk (FromPeg, ToPeg: Pegs; Which: Natural) IS
-- Auxiliary procedure implementing a 1-disk move
BEGIN
Ada.Text_IO.Put(Item => "Move disk ");
Ada.Integer_Text_IO.Put(Item => Which, Width => 1);
Ada.Text_IO.Put(Item => " from peg ");
Ada.Text_IO.Put(Item => FromPeg);
Ada.Text_IO.Put(Item => " to peg ");
Ada.Text_IO.Put(Item => ToPeg);
Ada.Text_IO.New_Line;
END MoveDisk;
PROCEDURE Tower (FromPeg, ToPeg, AuxPeg: Pegs; N: Natural) IS
-- Moves N disks from FromPeg to ToPeg
-- using AuxPeg as an auxiliary.
BEGIN -- Tower
IF N = 1 THEN
-- stopping case
MoveDisk(FromPeg, ToPeg, 1);
ELSE
-- recursive step
Tower (FromPeg, AuxPeg, ToPeg, N-1);
MoveDisk(FromPeg, ToPeg, N);
Tower (AuxPeg, ToPeg, FromPeg, N-1);
END IF;
END Tower;
BEGIN -- Test_Tower
Tower (FromPeg => 'A', ToPeg => 'B', AuxPeg => 'C', N => 5);
END Test_Tower;
Sample
RunMove disk 1 from peg A to peg B Move disk 2 from peg A to peg C Move disk 1 from peg B to peg C Move disk 3 from peg A to peg B Move disk 1 from peg C to peg A Move disk 2 from peg C to peg B Move disk 1 from peg A to peg B Move disk 4 from peg A to peg C Move disk 1 from peg B to peg C Move disk 2 from peg B to peg A Move disk 1 from peg C to peg A Move disk 3 from peg B to peg C Move disk 1 from peg A to peg B Move disk 2 from peg A to peg C Move disk 1 from peg B to peg C Move disk 5 from peg A to peg B Move disk 1 from peg C to peg A Move disk 2 from peg C to peg B Move disk 1 from peg A to peg B Move disk 3 from peg C to peg A Move disk 1 from peg B to peg C Move disk 2 from peg B to peg A Move disk 1 from peg C to peg A Move disk 4 from peg C to peg B Move disk 1 from peg A to peg B Move disk 2 from peg A to peg C Move disk 1 from peg B to peg C Move disk 3 from peg A to peg B Move disk 1 from peg C to peg A Move disk 2 from peg C to peg B Move disk 1 from peg A to peg BIn Program 13.9, the stopping case (move disk 1) is implemented as a call to procedure
MoveDisk. Each recursive step consists of two recursive calls to
Tower with a call to MoveDisk sandwiched between
them. The first recursive call solves the problem of moving N-1
disks to the auxiliary peg. The call to MoveDisk displays a
message to move disk N to the to peg.The second recursive
call solves the problem of moving the N-1 disks back from the
auxiliary peg to the to peg.
TESTING
The procedure call statement
Tower (FromPeg => 'A',ToPeg => 'C',AuxPeg => 'B',N => 3);
solves
a simpler three-disk problem: Move three disks from peg A to peg C. Its
execution is traced in
Figure
13.8. Verify for yourself that this list of steps does indeed solve the
three-disk problem.
Figure 13.8
Tower ('A', 'B', 'C', 3)
It is interesting to consider that procedure Tower in
Program
13.9 will solve the Tower of Hanoi Problem for any number of disks.The
three-disk problem results in a total of seven calls to procedure
Tower and is solved by seven disk moves. The five-disk problem
results in a total of 31 calls to procedure Tower and is solved in
31 moves. In general, the number of moves required to solve the n-disk
problem is 2n - 1: We say that it is a
O(2n) problem. Because each procedure call requires the
allocation and initialization of a local data area in memory, the computer time
increases exponentially with the problem size. For this reason, be careful
about running this program with a value of N that is larger than
10.
The dramatic increase in processing time for larger towers is a function of this problem, not recursion. In general, however, if there are recursive and iterative solutions to the same problem, the recursive solution requires more time and space because of the extra procedure calls.
Although recursion was not really needed to solve the simpler problems in this chapter, it was extremely useful in formulating an algorithm for Towers of Hanoi. For certain problems, recursion leads naturally to solutions that are much easier to read and understand than their iterative counterparts. In those cases, the benefits gained from increased clarity far outweigh the extra cost in time and memory of running a recursive program.
Many would argue that the recursive programs are esthetically more pleasing. They are indeed often more compact. Once you are accustomed to thinking recursively, the recursive form is somewhat easier to read and understand than the iterative form.
Some programmers like to use recursion as a conceptual tool. Once they have written the recursive form of a function or procedure, they can translate it into an iterative version if run-time efficiency is a major concern.
The next problem is a good illustration of the power of recursion. As for the Towers of Hanoi problem, its solution is relatively easy to write recursively; however, the problem would be much more difficult without using recursion. Unlike Towers of Hanoi, which is a cute and popular exercise, picture-processing algorithms have real application.
PROBLEM SPECIFICATION
We have a two-dimensional grid G of cells, each of which may be
empty or filled. The filled cells that are connected form a blob. There
may be several blobs on the grid. We would like a function that accepts as
input the coordinates of a particular cell and returns the size of the blob
containing the cell.
There are three blobs in the sample grid in
Figure
13.9. If the function parameters represent the X and
Y coordinates of a cell, the result of
BlobSize(G,3,4) is 5, the result of BlobSize(G,1,2)
is 2, the result of BlobSize(G,5,5) is 0, and the result of
BlobSize(G,5,1) is 4.
Figure 13.9
1 2 3 4 5
---------------------------
1 | | X | | | X |
---------------------------
2 | X | | | X | X |
---------------------------
3 | | | X | X | |
---------------------------
4 | X | | | | |
---------------------------
5 | X | X | X | | |
---------------------------
ANALYSIS
Function BlobSize must test the cell specified by its arguments to
see whether it is filled. There are two stopping cases: The cell (X,
Y) is not on the grid, or the cell (X, Y) is empty. In
either case, the value returned by BlobSize is 0. If the cell is
on the grid and filled, the value returned is 1 plus the size of the blobs
containing each of its eight neighbors. To avoid counting a filled cell more
than once, we will mark it as empty once we have visited it.
Data Requirements
Problem Inputs
the grid (Grid: BlobArray)
the X and Y coordinates of the point being visited
(X, Y : Integer)
Problem Outputs
the number of the cells in the blob containing point (X, Y)
DESIGN
Algorithm
1. IF cell (X, Y) is not in the array THEN
2. Return a count of 0
ELSIF cell (X, Y) is empty, then
3. Return a count of 0
ELSE
4. Mark cell (X, Y) as empty
5. Add 1 and see whether the blob contains any of the eight neighbors of cell (X, Y)
END IF;
Function BlobSize is shown in
Program
13.10, assuming the declarations below. The array type
BlobArray has element values Filled or
Empty. The array G has, as usual, bounds
G'Range(1) for the rows and G'Range(2) for the
columns.
Program 13.10
WITH Ada.Text_IO;
WITH Ada.Integer_Text_IO;
PROCEDURE Test_Blob_Size IS
------------------------------------------------------------------------
--| Illustrates the recursive function BlobSize, which computes
--| size of a "blob" or group of filled cells on a grid.
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: July 1995
------------------------------------------------------------------------
TYPE Fill IS (Empty, Filled);
TYPE BlobArray IS ARRAY (Integer RANGE <>,Integer RANGE <>) OF Fill;
Test: BlobArray(1..5,1..5);
PROCEDURE DisplayGrid(Grid: BlobArray) IS
-- Pre: Grid is defined
-- Post: displays Grid on the screen
BEGIN -- DisplayGrid
FOR Column IN Grid'Range(2) LOOP -- top border
Ada.Text_IO.Put(Item => "----");
END LOOP;
Ada.Text_IO.Put(Item => '-');
Ada.Text_IO.New_Line;
FOR Row IN Grid'Range(1) LOOP
FOR Column IN Grid'Range(2) LOOP
IF Grid(Row, Column) = Filled THEN
Ada.Text_IO.Put(Item => "| X ");
ELSE
Ada.Text_IO.Put(Item => "| ");
END IF;
END LOOP;
Ada.Text_IO.Put(Item => '|');
Ada.Text_IO.New_Line;
FOR Column IN Grid'Range(2) LOOP -- after each row
Ada.Text_IO.Put(Item => "----");
END LOOP;
Ada.Text_IO.Put(Item => '-');
Ada.Text_IO.New_Line;
END LOOP;
END DisplayGrid;
FUNCTION BlobSize(Grid : BlobArray; X, Y: Integer) RETURN Natural IS
-- Counts the number of filled cells in the blob containing
-- point (X, Y).
-- Pre : Blob array Grid and point (X,Y) are defined.
-- Post: Returns the size of the blob containing point (X, Y).
-- Resets the status of each cell in the blob to Empty.
CopyOfGrid : BlobArray(Grid'Range(1),Grid'Range(2));
-- because functions can't modify
-- their parameters, in Ada
FUNCTION Blob (X, Y : Integer) RETURN Natural IS
-- Inner function that performs the counting operation for BlobSize
-- Pre : Global array CopyOfGrid and point (X,Y) are defined.
-- Post: Returns the size of the blob containing point (X, Y).
-- Resets the status of each cell in the blob to Empty.
Result: Natural;
BEGIN -- Blob
IF (X NOT IN CopyOfGrid'Range(1)) OR
(Y NOT IN CopyOfGrid'Range(2)) THEN
Result := 0; -- cell not in grid
ELSIF CopyOfGrid(X, Y) = Empty THEN
Result := 0; -- cell is empty
ELSE -- cell is filled
-- recursive step
CopyOfGrid(X, Y) := Empty;
Result := 1 + Blob(X-1, Y+1) + Blob(X, Y+1) +
Blob(X+1, Y+1) + Blob(X+1, Y) +
Blob(X+1, Y-1) + Blob(X, Y-1) +
Blob(X-1, Y-1) + Blob(X-1, Y);
END IF;
RETURN Result;
END Blob;
BEGIN
CopyOfGrid := Grid;
RETURN Blob(X,Y);
END BlobSize;
BEGIN -- Test_Blob_Size
Test := ((Empty, Filled, Empty, Empty, Filled),
(Filled, Empty, Empty, Filled, Filled),
(Empty, Empty, Filled, Filled, Empty ),
(Filled, Empty, Empty, Empty, Empty ),
(Filled, Filled, Filled, Empty, Empty ));
DisplayGrid (Grid => Test);
Ada.Text_IO.Put(Item => "BlobSize(3,4) is ");
Ada.Integer_Text_IO.Put(Item => BlobSize(Test,3,4), Width => 1);
Ada.Text_IO.New_Line;
Ada.Text_IO.Put(Item => "BlobSize(1,2) is ");
Ada.Integer_Text_IO.Put(Item => BlobSize(Test,1,2), Width => 1);
Ada.Text_IO.New_Line;
Ada.Text_IO.Put(Item => "BlobSize(5,5) is ");
Ada.Integer_Text_IO.Put(Item => BlobSize(Test,5,5), Width => 1);
Ada.Text_IO.New_Line;
Ada.Text_IO.Put(Item => "BlobSize(5,1) is ");
Ada.Integer_Text_IO.Put(Item => BlobSize(Test,5,1), Width => 1);
Ada.Text_IO.New_Line;
END Test_Blob_Size;
Sample
Run--------------------------- | | X | | | X | --------------------------- | X | | | X | X | --------------------------- | | | X | X | | --------------------------- | X | | | | | --------------------------- | X | X | X | | | --------------------------- BlobSize(3,4) is 5 BlobSize(1,2) is 2 BlobSize(5,5) is 0 BlobSize(5,1) is 4
The
auxiliary function Blob in
Program
13.10, declared within BlobSize, implements the counting
algorithm; function BlobSize simply calls the recursive function
Blob, passing on its arguments, and returns the count computed by
function Blob as its own result. The purpose of the auxiliary
function is to protect the actual array from being modified when filled cells
are reset to empty by function Blob. We will come back to this
point shortly.
If the cell being visited is off the grid or is empty, a value of zero is
returned immediately. Otherwise, the recursive step executes, causing function
Blob to call itself eight times; each time, a different neighbor
of the current cell is visited. The cells are visited in a clockwise manner,
starting with the neighbor above and to the left. The function result is
defined as the sum of all values returned from these recursive calls plus 1
(for the current cell).
The sequence of operations performed in function Blob is
important. The IF statement tests whether the cell (X,
Y) is on the grid before testing whether (X, Y) is empty.
If the order were reversed, Constraint_Error would be raised
whenever (X, Y) was off the grid.
Also, the recursive step resets Grid(X,Y) to Empty
before visiting the neighbors of cell (X, Y). If this were not
done first, cell (X, Y) would be counted more than once because
it is a neighbor of all its neighbors. A worse problem is that the recursion
would not terminate. When each neighbor of the current cell is visited,
Blob is called again with the coordinates of the current cell as
arguments. If the current cell is Empty, an immediate return
occurs. If the current cell is still Filled, the recursive step
would be executed erroneously. Eventually the program will run out of time or
memory space; the latter is signaled in Ada by the raising of
Storage_Error.
A side effect of the execution of function Blob is that all
cells that are part of the blob being processed are reset to
Empty. This is the reason for using two functions. Because the
array is passed as a parameter to function BlobSize, a local copy
CopyOfGrid is saved when BlobSize is first called.
Only this local array is changed by function Blob, not the actual
array. If the counting operation were performed in function
BlobSize instead of in function Blob, eight copies of
this array would be made each time the recursive step was executed. Using the
function Blob and the array that is global to all recursive calls
of Blob (but still local to BlobSize) prevents the
unnecessary copying.
BlobSize for the coordinate
pairs (1, 1) and (1, 2) in the sample grid.
BlobSize
critical? What happens if we reverse them or combine them into a single
condition?
Copyright © 1996 by Addison-Wesley Publishing Company, Inc.