Sorting Algorithms  - continued

  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:
  • 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);
                 if number > 1 then doit (number - 1)

In COBOL, we would implement this as follows:

                 MOVE   1    TO STACK-PTR
                 PERFORM DOIT
                   UNTIL STACK-PTR = ZERO

                 SUBTRACT 1 FROM STACK-PTR
                 IF NUMBER > 1
                     SUBTRACT 1 FROM NUMBER
                     ADD      1 TO   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);
                     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)

                  WRITE (OUT, "NBR OF DISKS = "); READ (IN, M);
                  IF M > 0 THEN MOVE (M, "SOURCE", "DEST", "SPARE")
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.
             000400 AUTHOR.        LEIF SVALGAARD.
             000500 DATE-WRITTEN.  91/04/22
             000600     -REVISED:  91/05/01.
             000800 ENVIRONMENT DIVISION.
             001000 CONFIGURATION SECTION.
             001400 DATA DIVISION.
             001600 WORKING-STORAGE SECTION.
             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).
             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).
             003600 01  GLOBAL-VARIABLES.
             003700     02  SWAP-ROD                PIC X(6).
             003800     02  WHAT-TO-DO              PIC 9(1).
             004000 PROCEDURE DIVISION.
             004100 BEGIN-PROGRAM.
             004200     DISPLAY "NBR OF DISKS = " NO ADVANCING
             004300     ACCEPT THE-DISK-NBR
             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     .
             005400 MOVE-DISK.
             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     .
             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     .
             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     .
             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     .
             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.

This website is copyrighted by Leif Svalgaard.
Last Updated: May 6, 2001