1. 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:

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