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
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.
007800     IF THE-DISK-NBR > 1
007900         SUBTRACT 1 FROM THE-DISK-NBR
008000         MOVE WHAT-TO-DO TO THE-WHAT
008200         MOVE LOCAL-VARIABLES TO STACK-ITEM (STACK-PTR)
008400     .
008500
008600 SHOW-DISK-MOVED.
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.

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