Date:         Mon, 13 Jul 1998 12:30:08 -0400
Reply-To:     "Paul M. Dorfman" <pdorfma@UCS.ATT.COM>
Sender:       "SAS(r) Discussion" <SAS-L@UGA.CC.UGA.EDU>
From:         "Paul M. Dorfman" <pdorfma@UCS.ATT.COM>
Organization: Citibank Universal Card Services
Subject:      Re: Modular recursion in COBOL and SAS (was: Re:Recursion in
              SAS-the exact query)
Content-Type: text/plain; charset=us-ascii

Ian Whitlock <whitloi1@westat.com>, in particular, wrote:
 
>   I once was almost thrown out of a COBOL training program on my first
>   programming job when I innocently asked if COBOL could make recursive
>   calls to performs.
 
Ian,
 
Curiously enough, COBOL can make recursive calls to PERFORMs. Years ago, I had
to write a COBOL routine that would traverse a non-binary hierarchical tree and
"collect" its leaf nodes. Once a new non-leaf node is encountered, the same
algorithm should start all over again, so it was fairly apparent that  a
recursive code would look something like
 
   1000-TRAVERSE.
          ...PERFORM SOMETHING...
          IF   SOME-CONDITION
                PERFORM 1000-TRAVERSE
          ELSE
          ...PERFORM SOMETHING-ELSE...
          END-IF
    .
    PERFORM 1000-TRAVERSE
 
Of course, this is not a recursive function call, but a recursive process
still.
However, coded this way, the program did not work. The compiler would issue a
warning, yet compile anyway. After some number of properly done recursive calls
the program would usually abend with S0C4.  Contrary to that , once the
recursive PERFORM was replaced by GO TO, everything worked just fine, even
though the warning persisted.
 
(Needless to say, both recursion and GO TO were severely against the shop's
COBOL standards. The only reason I was not fired was because nobody figured out
how to do the same iteratively in spite of loud bragging to the contrary).
 
Back then, I figured out (maybe, wrong) that the difference was due to the
PERFORM behavior behind the scenes: "execute the paragraph, then go to the next
instruction", and the next instruction was nowhere to be found. So, the program
wild-branched to a deliberate location, usually invading a foreign memory
region, hence bombing with S0C4.
 
It was very interesting to find out whether  SAS would be as unfriendly as
COBOL
if an attempt were made to implement a recursive call to LINK, SAS's analog of
PERFORM. Can SAS swallow a self-LINK  without choking?  Let us consider an
example. Suppose we have an unsorted array. We want to place its first element
A(1) where it would be if the array were sorted ascending, so that all elements
less than A(1) would be to the left of its final location, and all the elements
greater than A(1) - to the right. (Of course, you have recognized the basic
building block of Quicksort). One way to code the process would be:
 
29  DATA _NULL_;
30       ARRAY A(9) (4,7,3,1,9,6,2,8,5);
31
32       KEY   =  1;
33       PIVOT =  9;
34       STEP  = -1;
35
36       IF 0 THEN DO;
37           PART:
38           DO J=1 TO 9; PUT A(J) @; END; PUT; *SHOW CURRENT STATE OF
ARRAY;
39           DO I = PIVOT TO KEY BY STEP;
40                 IF STEP * (A(I) - A(KEY)) > 0 THEN DO;
41                      T=A(I); A(I)=A(KEY); A(KEY)=T; *SWAP ELEMENTS;
42                      PIVOT = KEY - STEP;
43                      KEY   = I;
44                      STEP  = (-1) * STEP; *SWAP SWEEP DIRECTION;
45                      LINK PART; *CALL ITSELF;
46                 END;
47           END;
48           RETURN;
49   END;
50
51   LINK PART;
52  RUN;
 
4 7 3 1 9 6 2 8 5
2 7 3 1 9 6 4 8 5
2 4 3 1 9 6 7 8 5
2 1 3 4 9 6 7 8 5
NOTE: The DATA statement used 0.05 CPU seconds and 3636K.
 
As we can see, the result is as expected, and SAS has no problem LINKing to
itself. Replacing the internal LINK with GOTO produces the same output.
 
By the way, this example also shows that, contrary to what some COBOL people
say, COBOL-type paragraphizing can be easily emulated in the SAS DATA step. A
LINK routine together with its label and  RETURN statement surrounded by "IF 0
THEN DO;" and "END;" does not execute unless called, and as such, can be placed
anywhere in the DATA step. On a number of occasions, I have found this method
quite handy, in particular, whenever heavy modularizing was desirable within
the
boundaries of the DATA step.
 
Could not avoid the temptation to toss my $.02 into this SASCOBOL bucket...
 
Most cordially, Paul.
 
+++++++++++++++++++++++++++++++++++++
Paul M. Dorfman
Citibank UCS Decision Support Systems
Jacksonville, FL
+++++++++++++++++++++++++++++++++++++