|
- Towers of Hanoi
Pseudo-recursive Programming
The Quicksort algorithm is a
perfect example of an algorithm which can best be expressed in a
recursive manner. This means that when one procedure calls another
(or itself) two things happen:
- instruction pointers are stacked so that at the end of the
called procedure, execution can continue in the calling
procedure.
- local data is also stacked, so that when the calling procedure
resumes, its local data is reinstated.
COBOL saves only one instruction pointer per paragraph, and has
no concept of local data. This is, of course, not true of the latest
Cobol standard, but often we have to labor in a legacy-setting
without the benefit of the latest technology.
We adapt to the limitations of COBOL by using a stack to store
`requests' and a loop which takes the next request and processes it.
A `recursive' call is in the form of new requests, which are
stacked. When the stack is empty, all recursive calls have been
processed. Any local data is also stacked.
Take an (unrealistic) Pascal procedure which does a recursive
call:
procedure doit (number: integer);
begin
if number > 1 then doit (number - 1)
end;
In COBOL, we would implement this as follows:
EXAMPLE.
MOVE 1 TO STACK-PTR
MOVE NUMBER TO STACKED-NUMBER (STACK-PTR)
PERFORM DOIT
UNTIL STACK-PTR = ZERO
.
DOIT.
MOVE STACKED-NUMBER (STACK-PTR) TO NUMBER
SUBTRACT 1 FROM STACK-PTR
IF NUMBER > 1
SUBTRACT 1 FROM NUMBER
ADD 1 TO STACK-PTR
MOVE NUMBER TO STACKED-NUMBER (STACK-PTR)
.
A good way to understand this technique is to take a recursive
procedure such as a tree-printing algorithm, and to implement it in
COBOL. We show below the famous `Towers of Hanoi' problem
1. Towers of Hanoi
In a monastery in Hanoi there are three diamond rods. God placed
64 gold disks of different sizes - each with a central hole- on rod
number 1 such that the largest disk is at the bottom of the stack
and the smallest disk is on top. The monks' mission is to move all
the disks onto rod number 2. Only one disk may be moved at a time
and never may a larger disk be placed on a smaller one. If needed,
disks may temporarily be placed on the third rod, again in such a
manner that no larger disk rests on a smaller one.
This classical problem can be solved by a recursive procedure
that first moves all disks except the last one from the source rod
to the spare rod, then moves the last - and largest - disk from the
source rod to its final position on the destination rod, and finally
moves all disks from the spare rod to the destination rod. Moving
N-1 disks is then performed in the same manner recursively until all
disks have been moved:
BEGIN INTEGER M;
PROCEDURE MOVE (N, SOURCE, DEST, SPARE);
INTEGER N; STRING SOURCE, DEST, SPARE;
BEGIN
IF N > 1 THEN MOVE (N-1, SOURCE, SPARE, DEST);
WRITE (OUT, "MOVE DISK ", N,
" FROM ", SOURCE,
" TO " , DEST);
IF N > 1 THEN MOVE (N-1, SPARE, DEST, SOURCE)
END;
WRITE (OUT, "NBR OF DISKS = "); READ (IN, M);
IF M > 0 THEN MOVE (M, "SOURCE", "DEST", "SPARE")
END
The COBOL version of the program follows below. As we wish to
illustrate pseudo-recursion rather than input/output, we
exceptionally tolerate a non-portable program that uses ACCEPT and
DISPLAY. The program counter is explicitly managed with the variable
WHAT-TO-DO and parameters (which are in a sense local to each
invocation of the procedure) are stacked along with the program
counter. The call of the procedure in the main program is simulated
by stacking the first set of parameters.
000100 IDENTIFICATION DIVISION.
000200 PROGRAM-ID. HANOI.
000300
000400 AUTHOR. LEIF SVALGAARD.
000500 DATE-WRITTEN. 91/04/22
000600 -REVISED: 91/05/01.
000700
000800 ENVIRONMENT DIVISION.
000900
001000 CONFIGURATION SECTION.
001100 SOURCE-COMPUTER. ALMOST-PORTABLE.
001200 OBJECT-COMPUTER. ALMOST-PORTABLE.
001300
001400 DATA DIVISION.
001500
001600 WORKING-STORAGE SECTION.
001700
002000 01 STACK-SPACE.
002100 02 STACK-PTR PIC S9(3) COMP.
002200 02 STACK-ITEM OCCURS 64.
002300 03 DISK-NBR PIC 9(2).
002400 03 SOURCE-ROD PIC X(6).
002500 03 DEST-ROD PIC X(6).
002600 03 SPARE-ROD PIC X(6).
002700 03 WHAT PIC 9(1).
002800
002900 01 LOCAL-VARIABLES.
003000 02 THE-DISK-NBR PIC 9(2).
003100 02 THE-SOURCE-ROD PIC X(6) VALUE "SOURCE".
003200 02 THE-DEST-ROD PIC X(6) VALUE "DEST".
003300 02 THE-SPARE-ROD PIC X(6) VALUE "SPARE".
003400 02 THE-WHAT PIC 9(1).
003500
003600 01 GLOBAL-VARIABLES.
003700 02 SWAP-ROD PIC X(6).
003800 02 WHAT-TO-DO PIC 9(1).
003900
004000 PROCEDURE DIVISION.
004100 BEGIN-PROGRAM.
004200 DISPLAY "NBR OF DISKS = " NO ADVANCING
004300 ACCEPT THE-DISK-NBR
004400
004500 IF THE-DISK-NBR > ZERO
004600 MOVE 1 TO STACK-PTR, WHAT-TO-DO
004700 MOVE LOCAL-VARIABLES TO STACK-ITEM (1)
004800 PERFORM MOVE-DISK
004900 UNTIL STACK-PTR = ZERO
005000 .
005100 STOP RUN
005200 .
005300
005400 MOVE-DISK.
005500 MOVE STACK-ITEM (STACK-PTR) TO LOCAL-VARIABLES
005600 IF WHAT-TO-DO = 1
005700 PERFORM MOVE-DISKS-AWAY
005800 ELSE
005900 IF WHAT-TO-DO = 2
006000 PERFORM SHOW-DISK-MOVED
006100 ELSE
006200 IF WHAT-TO-DO = 3
006300 PERFORM MOVE-DISKS-BACK
006400 ELSE
006500 MOVE WHAT (STACK-PTR) TO WHAT-TO-DO
006600 SUBTRACT 1 FROM STACK-PTR
006700 .
006800
006900 MOVE-DISKS-AWAY.
007000 MOVE THE-SPARE-ROD TO SWAP-ROD
007100 MOVE THE-DEST-ROD TO THE-SPARE-ROD
007200 MOVE SWAP-ROD TO THE-DEST-ROD
007300 PERFORM MOVE-THE-DISKS
007400 .
007500
007600 MOVE-THE-DISKS.
007700 ADD 1 TO WHAT-TO-DO
007800 IF THE-DISK-NBR > 1
007900 SUBTRACT 1 FROM THE-DISK-NBR
008000 MOVE WHAT-TO-DO TO THE-WHAT
008100 ADD 1 TO STACK-PTR
008200 MOVE LOCAL-VARIABLES TO STACK-ITEM (STACK-PTR)
008400 .
008500
008600 SHOW-DISK-MOVED.
008700 ADD 1 TO WHAT-TO-DO
008800 DISPLAY "MOVE DISK " THE-DISK-NBR
008900 " FROM " THE-SOURCE-ROD
009000 " TO " THE-DEST-ROD
009100 .
009200
009300 MOVE-DISKS-BACK.
009400 MOVE THE-SPARE-ROD TO SWAP-ROD
009500 MOVE THE-SOURCE-ROD TO THE-SPARE-ROD
009600 MOVE SWAP-ROD TO THE-SOURCE-ROD
009700 PERFORM MOVE-THE-DISKS
009800 .
In a small program like this, the extra machinery needed to handle
the recursion looms large. In realistic programs - like the
Structure Analyser in the following example - the extra code to
implement recursion is negligible. If a problem is inherently
recursive - and many are - it pays to think recursively and use the
pseudo-recursive techniques shown here. It is no excuse to say:
COBOL does not support recursion directly, therefore I cannot solve
my problem. The programming language used is very rarely the true
blocking factor.
It is often said that recursion is too expensive in terms of
overhead. This is only true for trivial, small programs that use
recursion where simple iteration should have been used. In realistic
programs, recursion is not in the inner loop anyway and thus carries
little or no run-time penalty. It is also not true that recursion is
difficult or esoteric to use.
|
|