Simulated Recursion

Earl is a senior consultant with Keane Inc., a Boston-based IT consulting firm. He can be contacted at earl.augusta@ corporate.ge.com.

In the early 1960s, C.A. Hoare developed the Quicksort sorting process. Quicksort divides the data into successively smaller groups. In itself this does not sound very impressive, but tests show that Quicksort can sort large volumes of data tens or hundreds of times faster than most commonly used algorithms. However, there is a problem.

Quicksort uses recursion, the process by which a procedure or a function calls itself. Recursion is very powerful in attacking problems where the same questions are repeated and the same actions are performed, but with each set of actions working with the result of a prior step. Examinations of data structures such as linked lists and trees are ideally suited for recursive programming. In languages such as C or Pascal, recursion is allowed, but languages like Cobol generally forbid recursion. A way around language limitations is to simulate recursion in a manner that can be coded in almost all programming languages.

A recursed program examines and acts upon data until it arrives at a point where logic suggests that there is a new set of data, ready to be acted upon by a new copy of the program being executed. At this point, the program calls itself. Normally this calling passes the new data to be processed by the next iteration. Eventually, the logic dictates that further recursion is unnecessary, and the current active version of the code falls out the bottom, returning to execute the instruction following the one that issued the call in the prior iteration of the recursive module. As each copy of the code finishes, it transmits information back to the calling copy. When control is finally passed to the original copy of the recursive module, falling out the bottom terminates the recursive process.

Simulating Recursion

Knowing the process by which recursion passes data upward and downward through the called modules, you can isolate and preserve the variables unique to each recursive step and simply loop a given piece of code to achieve simulated recursion. Since looping would start the code process at the same place each time, you must keep a place marker, indicating just where to begin the processing of the current iteration.

The data used by each iterative step can be in any form and is a function of the programming requirements. A binary switch is probably the best form for a place marker. A combination of the required variable data and a place marker form a snapshot of the conditions during any step of the recursion. You should construct a table where snapshots can be stored. A pointer to this stack of snapshots allows the program to select the appropriate set of values for a particular iteration of the recursive process. The depth of the stack must be such that it can contain all the steps necessary to achieve the objective of the program being executed.

Simulated Recursion in Quicksort Example

The examples I present here demonstrate simulated recursion Quicksort in a Cobol program. This is one of the most hostile and awkward environments in which to do recursive programming. The idea is, "If we can do it here, we can do it anywhere." The data portion of Quicksort would look like Listing One.

In Listing One, a table of 32,000 100-byte entries is the data to be sorted. SWAP-ELEMENT and PIVOT-VALUE represent scratch work areas required to hold individual table entries from time to time. The WORKING-INDEXES point to table entries and, as such, are full-word integers. FURST and LAAST are pointers to the first and last table entries in a group currently under consideration. The size and location of that group changes constantly during the progress of Quicksort.

HOW-RETURN is the place marker enabling the program to begin processing at the correct place when reentering the looped code. The place-marker concept is critical to enabling fixed, looped code to emulate recursive processing.

The TABLE-OF-INDEXES is a stack of WORKING-INDEXES. As the program progresses downward (calling another iteration of QUICKSORT) or upward (returning to a prior iteration) the values for pointers and place markers are saved or retrieved. Every occurrence within the TABLE-OF-INDEXES is one set of WORKING-INDEXES. The SESSION-INDEX is the pointer to the set of values currently being used. LEFT and RIGHT-INDEX are working pointers used during each phase of Quicksort.

Listing Two initializes Quicksort. It presets the stack of working pointers to binary zero bits. Then, one set of working pointers is initialized, with the FURST pointer set to point to the first element in the data to be sorted and LAAST set to point to the last. Setting the HOW-RETURN switch to 1 indicates that this is a new iteration of the Quicksort code and processing should begin at the beginning. The SESSION-INDEX is set to 1 (this will be the first session) and the data is loaded onto the stack.

Each iteration of the code in Listing Three first pulls data from the stack and then puts it into the WORKING-INDEXES. The value of the SESSION-INDEX determines which data is pulled. By controlling the values for the SESSION-INDEX and the HOW-RETURN switch, you control how each program loop functions.

The program logic in Listing Four examines a specific group of table elements. Even though the members under consideration change continually, the examination process is exactly the same; hence the application of recursive processing.

The program logic establishes the first element to be a pivot point around which other comparisons will be made. Elements are examined from left to right, and from right to left, and element swaps are made where indicated. The end result is that the pivot element has been relocated and now divides the group into two smaller groups, where all elements to the left of the pivot are smaller than the pivot, and all elements to the right are larger. This produces two new, smaller groups that are then examined in the same manner.

Listing Five prepares the Quicksort environment to examine first the left side, and then the right side of the two newly created strings of data to be sorted. When the index values have been set, the program simply calls Quicksort again. After Quicksort examines both strings and returns control to this iteration of the code, the program tests to see if this iteration is the first one that initiated the sort. If that is the case, the sort is complete. If not, the pointer to session data is reduced by one and, in effect, when Quicksort is called again (see Listing Six), control is returned to the prior program iteration.

What is the difference between a typical user sort, where every element is compared against every other element, and a recursive Quicksort? In large volume sorting operations, the differences are impressive. Recursive Quicksort could mean saving minutes or even hours when sorting large amounts of data. The recursive process is very powerful and has many uses in mathematical analysis. Quicksort is only one application of this type of programming logic.

Conclusion

While this example illustrates the use of a simulated recursion Quicksort in Cobol, this process can be used in many other types of languages including C and Pascal. The use of the recursive Quicksort can greatly reduce the time needed to sort large amounts of data, which can be useful regardless of the programming language.

DDJ

Listing One

 01  TABLE-TO-BE-SORTED.
     02 TABLE-ENTRY   PIC X(100) OCCURS 32000 TIMES.
*
 01  SWAP-ELEMENT     PIC X(100).
 01  PIVOT-VALUE      PIC X(100).
*
 01  WORKING-INDEXES.
     02 FURST         PIC 9(5) USAGE BINARY.
     02 LAAST         PIC 9(5) USAGE BINARY.
     02 PIVOT         PIC 9(5) USAGE BINARY.
     02 HOW-RETURN    PIC 9(5) USAGE BINARY.
*
 01  TABLE-OF-INDEXES.
     02 CURRENT-INDEXES OCCURS 100 TIMES.
         03 FILLER    PIC 9(5) USAGE BINARY.
         03 FILLER    PIC 9(5) USAGE BINARY.
         03 FILLER    PIC 9(5) USAGE BINARY.
         03 FILLER    PIC 9(5) USAGE BINARY.
 01  SESSION-INDEX    PIC 9(5) USAGE BINARY.
*
 01  LEFT-INDEX       PIC 9(5) USAGE BINARY.
 01  RIGHT-INDEX      PIC 9(5) USAGE BINARY.

Back to Article

Listing Two

 INITIALIZE-SORT.

     MOVE LOW-VALUES TO TABLE-OF-INDEXES.
     MOVE 1 TO FURST
               HOW-RETURN
               SESSION-INDEX.
     MOVE 32000 TO LAAST.
     MOVE WORKING-INDEXES TO
         CURRENT-INDEXES (SESSION-INDEX).

Back to Article

Listing Three

CALL-QUICKSORT.
     MOVE CURRENT-INDEXES (SESSION-INDEX) TO
         WORKING-INDEXES.
     IF HOW-RETURN = 2 GO TO DO-PIVOT-TO-LAST.
     IF HOW-RETURN = 3 GO TO SEE-IF-WE-ARE-ALL-DONE.
     IF FURST NOT < LAAST GO TO SEE-IF-WE-ARE-ALL-DONE.

Back to Article

Listing Four

 SPLIT-THE-LIST.
     MOVE TABLE-ENTRY (FURST) TO PIVOT-VALUE.
     MOVE FURST TO LEFT-INDEX.
     COMPUTE RIGHT-INDEX = LAAST + 1.
     PERFORM WITH TEST AFTER UNTIL
             RIGHT-INDEX <= LEFT-INDEX
         PERFORM WITH TEST AFTER UNTIL
             TABLE-ENTRY (LEFT-INDEX) >= PIVOT-VALUE
             ADD 1 TO LEFT-INDEX
         END-PERFORM
         PERFORM WITH TEST AFTER UNTIL
             TABLE-ENTRY (RIGHT-INDEX) <= PIVOT-VALUE
             SUBTRACT 1 FROM RIGHT-INDEX
         END-PERFORM
         IF LEFT-INDEX < RIGHT-INDEX
             PERFORM EXCHANGE-TWO-ELEMENTS
         END-IF
     END-PERFORM.
     MOVE FURST TO LEFT-INDEX.
 EXCHANGE-TWO-ELEMENTS.
     MOVE TABLE-ENTRY (LEFT-INDEX) TO ENTRY-HOLDER.
     MOVE TABLE-ENTRY (RIGHT-INDEX) TO
          TABLE-ENTRY (LEFT-INDEX).
     MOVE ENTRY-HOLDER TO TABLE-ENTRY (RIGHT-INDEX).
 EXCHANGE-TWO-ELEMENTS-EXIT.
     MOVE RIGHT-INDEX TO PIVOT.

Back to Article

Listing Five

 DO-FIRST-TO-PIVOT.
     MOVE 2 TO HOW-RETURN.
     MOVE WORKING-INDEXES TO
         CURRENT-INDEXES (SESSION-INDEX).
     COMPUTE LAAST = PIVOT - 1.
     MOVE 1 TO HOW-RETURN.
     ADD 1 TO SESSION-INDEX.
     MOVE WORKING-INDEXES TO 
         CURRENT-INDEXES (SESSION-INDEX).
     GO TO CALL-QUICKSORT.

*
 DO-PIVOT-TO-LAST.
     MOVE 3 TO HOW-RETURN.
     MOVE WORKING-INDEXES TO 
         CURRENT-INDEXES (SESSION-INDEX).
     COMPUTE FURST = PIVOT + 1.
     MOVE 1 TO HOW-RETURN.
     ADD 1 TO SESSION-INDEX.
     MOVE WORKING-INDEXES TO
         CURRENT-INDEXES (SESSION-INDEX).
     GO TO CALL-QUICKSORT.

Back to Article

Listing Six

*
 SEE-IF-WE-ARE-ALL-DONE.
     SUBTRACT 1 FROM SESSION-INDEX.
     IF SESSION-INDEX > 0
         GO TO CALL-QUICKSORT.
     STOP RUN.

Back to Article