Recursive COBOL

A recursive subroutine calls itself, and in COBOL that needs three things: the program declares IS RECURSIVE, its temporary fields live in LOCAL-STORAGE so that each call has its own copy, and it is compiled as a module rather than as a whole program. This lesson builds a factorial and then breaks it on purpose.

What recursion needs

The factorial of five is 5 × 4 × 3 × 2 × 1, and the recursive definition is n × factorial(n - 1) with one as the base case. A program that computes it that way has two values alive at every level: the n it was called with and the result of the level below. Both must belong to the call, not to the program, or the deeper call overwrites the values the shallower one still needs.

WORKING-STORAGE belongs to the program and exists once. LOCAL-STORAGE is allocated at each CALL and discarded at the return, which is exactly the per-call copy a recursive subroutine needs. This compiler does not allow LOCAL-STORAGE in a nested program, so the subroutine has to be compiled as a module of its own:

The recursive module

The module takes the number and the result through its LINKAGE SECTION, keeps its two temporaries in LOCAL-STORAGE and calls itself for the next lower number:

IDENTIFICATION DIVISION. PROGRAM-ID. FACT IS RECURSIVE. DATA DIVISION. LOCAL-STORAGE SECTION. 01 NEXT-N PIC 9(2). 01 NEXT-R PIC 9(8). LINKAGE SECTION. 01 IN-N PIC 9(2). 01 OUT-R PIC 9(8). PROCEDURE DIVISION USING IN-N OUT-R. IF IN-N <= 1 MOVE 1 TO OUT-R ELSE COMPUTE NEXT-N = IN-N - 1 CALL "FACT" USING NEXT-N NEXT-R COMPUTE OUT-R = IN-N * NEXT-R END-IF. EXIT PROGRAM. END PROGRAM FACT.

cobc -m factm.cob

cobc -m writes a loadable module and not an executable: a subroutine has no main, so there is nothing to run until a program calls it. The module file this command produced is factm.so, and the next program links it.

The program that calls it

The caller is the file main.cob: two lines of identification and then the divisions below. The listing starts at the data division on purpose, because the checker builds a free-format block on its own and this program needs the module; the two lines it leaves out are IDENTIFICATION DIVISION. and PROGRAM-ID. FACTMAIN.

DATA DIVISION. WORKING-STORAGE SECTION. 01 N-F PIC 9(2) VALUE 5. 01 RESULT-F PIC 9(8) VALUE 0. PROCEDURE DIVISION. CALL "FACT" USING N-F RESULT-F. DISPLAY N-F "! = " RESULT-F. STOP RUN. END PROGRAM FACTMAIN.

cobc -x -free -Wall -o fact main.cob factm.cob
./fact

05! = 00000120

The link line takes both sources, so the module travels inside the executable and no module path is needed at run time. The result is 120 in eight digits, the picture of RESULT-F, and the number prints in its two digits with the leading zero.

Without LOCAL-STORAGE

Move the two temporaries from LOCAL-STORAGE to WORKING-STORAGE and change nothing else:

DATA DIVISION. WORKING-STORAGE SECTION. 01 NEXT-N PIC 9(2). 01 NEXT-R PIC 9(8).

The fragment above is not a whole program, so the checker does not build it. Built with the same cobc -m and linked into the same caller, it prints 05! = 00000005 instead of 120. Every level of the recursion wrote into the same two fields, so the multiplication at the top of the stack used a value the deeper levels had already overwritten, and the run finished with the number it started from.

Nothing in the build or the run reports it: a recursive program with shared temporaries is legal COBOL that computes the wrong answer. The rule is the one the language gives with the section: the working data of a subroutine that calls itself lives in LOCAL-STORAGE or in the LINKAGE SECTION, never in the program storage.

Recursion is the last unusual shape this part teaches. The next lesson takes an ordinary sixty-line paragraph and splits it into four, with the same output as the proof, which is the change most old COBOL needs before anything else can be done to it.

Exercises

  1. Change N-F to 6 and run the program. What is 6!, and does it fit in PIC 9(8)?
  2. Remove IS RECURSIVE and build. What does the compiler say?
  3. Add a second argument that counts the depth of the recursion and print it in the base case. How deep does 5! go?
  4. Write the same factorial as a loop and compare the two programs: which is shorter, and which is easier to read for a reader who has never seen the definition?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does IS RECURSIVE declare?

    Answer

    That the program may call itself

    The clause allows the CALL of the program to re-enter it, which is otherwise refused.

  2. Which section gives every call its own copy of a temporary field?

    Answer

    LOCAL-STORAGE

    WORKING-STORAGE exists once per program, which is what breaks the factorial when the temporaries live there.

  3. Why is the recursive subroutine compiled with cobc -m?

    Answer

    It is a subroutine without a main, so it is built as a module and linked

    The module is linked into the caller with the same cobc -x line, and the result runs as one executable.

  4. What does the factorial print when the temporaries are in WORKING-STORAGE?

    Answer

    Five, the number it started from, because the levels share the fields

    The run measured on this page printed 00000005 with the shared fields and 00000120 with LOCAL-STORAGE.

  5. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q5. DATA DIVISION. WORKING-STORAGE SECTION. 01 N-F PIC 9(2) VALUE 4. 01 R-F PIC 9(6) VALUE 1. 01 I-F PIC 9(2) VALUE 1. PROCEDURE DIVISION. PERFORM VARYING I-F FROM 1 BY 1 UNTIL I-F IS GREATER THAN N-F MULTIPLY I-F BY R-F END-PERFORM. DISPLAY R-F. STOP RUN.

    Answer

    000024

    The loop multiplies one by 1, 2, 3 and 4, which is twenty-four.

  6. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q6. DATA DIVISION. WORKING-STORAGE SECTION. 01 N-F PIC 9(2) VALUE 3. 01 A-F PIC 9(4) VALUE 0. 01 B-F PIC 9(4) VALUE 0. PROCEDURE DIVISION. COMPUTE A-F = N-F * 2. COMPUTE B-F = N-F * N-F. DISPLAY A-F " " B-F. STOP RUN.

    Answer

    0006 0009

    Three doubled is six and three squared is nine, each in four digits.

  7. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q7. DATA DIVISION. WORKING-STORAGE SECTION. 01 C-F PIC 9(2) VALUE 0. PROCEDURE DIVISION. PERFORM ADD-ONE 3 TIMES. DISPLAY C-F. STOP RUN. ADD-ONE. ADD 1 TO C-F.

    Answer

    03

    The paragraph runs three times and adds one each time.

  8. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q8. DATA DIVISION. WORKING-STORAGE SECTION. 01 N-F PIC 9(2) VALUE 5. 01 R-F PIC 9(6) VALUE 0. PROCEDURE DIVISION. IF N-F IS GREATER THAN 3 MOVE 100 TO R-F ELSE MOVE 50 TO R-F END-IF. DISPLAY R-F. STOP RUN.

    Answer

    000100

    Five is greater than three, so the first branch stores a hundred.

  9. A recursive subroutine keeps the number it was called with in WORKING-STORAGE. What is wrong with that?

    Answer

    The deeper call overwrites it, so the shallower call multiplies by the wrong number

    That is the difference this page measured between 5 and 120.

  10. Why does this compiler refuse LOCAL-STORAGE in a nested program?

    Answer

    It is the limit of this version, so the subroutine is compiled as its own module

    The build fails with LOCAL-STORAGE not allowed in nested programs, which is why the page uses cobc -m.

The code on this page was built with cobc (GnuCOBOL) 3.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev