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 os 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") ENDThe 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.