Recursive procedures

An active procedure that is invoked from within itself or from within another active procedure is a recursive procedure. Such an invocation is called recursion.

A procedure that is invoked recursively must have the RECURSIVE attribute specified in the PROCEDURE statement.


>>-RECURSIVE---------------------------------------------------><

The environment (that is, values of automatic variables and the like) of every invocation of a recursive procedure is preserved in a manner analogous to the stacking of allocations of a controlled variable (see Controlled storage and attribute). Think of an environment as being pushed down at a recursive invocation, and popped up at the termination of that invocation. A label constant in the current block is always a reference to the current invocation of the block that contains the label.

If a label constant is assigned to a label variable in a particular invocation, and the label variable is not declared within the recursive procedure, a GO TO statement naming that variable in another invocation restores the environment that existed when the assignment was performed, terminating the current and any intervening procedures and begin-blocks.

The environment of a procedure that was invoked from within a recursive procedure by means of an entry variable is the one that was current when the entry constant was assigned to the variable. Consider the following example:

  I=1;
  call A;                                /* First invocation of A      */
   
  A: proc recursive;
     declare Ev entry variable static;
     if I=1 then
        do;
          I=2;
          Ev=B;
          call A;                        /* 2nd invocation of A        */
        end;
     else call Ev;                       /* Invokes B with environment */
                                         /* of first invocation of A   */
  B: proc;
     go to Out;
  end B;
  Out: end A;

The GO TO statement in the procedure B transfers control to the END A statement in the first invocation of A, and terminates B and both invocations of A.

Effect of recursion on automatic variables

The values of variables allocated in one activation of a recursive procedure must be protected from change by other activations. This is arranged by stacking the variables. A stack operates on a last-in, first-out basis. The most recent generation of an automatic variable is the only one that can be referenced. Static variables are not affected by recursion. Thus, they are useful for communication across recursive invocations. This also applies to automatic variables that are declared in a procedure that contains a recursive procedure and to controlled and based variables. In the following example:

  A: proc;
     dcl X;
     .
     .
     .
     B: proc recursive;
         dcl Z,Y static;
         call B;
        .
        .
        .
     end B;
   end A;

A single generation of the variable X exists throughout invocations of procedure B. The variable Z has a different generation for each invocation of procedure B. The variable Y can be referred to only in procedure B and is not reallocated at each invocation. (The concept of stacking variables is also of importance in the discussion of controlled variables in Controlled storage and attribute.)