Block Activation and Recursion

Each time a procedure block is called, it is said to be active, and it remains active until it returns from the call (or until a non-local GOTO transfers control to a containing block activation). Such procedure activation has an associated block of storage allocated on a stack. This block of storage is called a stack frame, and it is used to hold information (such as the location to which control should return from the activation) that is unique to each procedure activation.

The stack frame contains storage for the automatic data declared within the block. Thus, each activation of the block has its own copy of the automatic data.

If procedure A calls procedure B, the stack frame associated with the activation of A is pushed down by the stack frame associated with the activation of B. When B returns, its stack frame is popped from the stack and the stack frame of A is then the current stack frame.

If procedure A calls itself directly or indirectly by invoking a chain of procedures in which A is again called, A is said to be a recursive procedure. For example:

A: PROCEDURE RECURSIVE;
      .
      .
      .
   CALL A;
      .
      .
      .
   END A;

The following example shows a program that makes a copy of a tree structure using block activation and recursion principles.

   .
   .
NEW = COPY(OLD);
   .
   .
COPY: PROCEDURE(IN) RETURNS(POINTER)| RECURSIVE;
      DECLARE     (IN,OUT) POINTER;
      DECLARE     1 RECORD BASED,
                        2 FIELD1 FLOAT, 
                        2 FIELD2 FLOAT, 
                        2 DAUGHTER POINTER,
                        2 SON POINTER;
DECLARE NULL BUILTIN;

IF IN = NULL THEN RETURN(NULL);
ALLOCATE RECORD SET(OUT);
OUT->RECORD.FIELD1 = IN->RECORD.FIELD1; 
OUT->RECORD.FIELD2 = IN->RECORD.FIELD2; OUT->RECORD.DAUGHTER =
      COPY(IN->RECORD.DAUGHTER);
OUT->RECORD.SON = COPY(IN->RECORD.SON); 
RETURN(OUT);

END COPY;

As demonstrated in this example, each record of the original tree structure may be linked using pointers to a SON record and/or a DAUGHTER record. Either the SON or the DAUGHTER field may contain a null pointer value. COPY is called with a pointer to the root in the original tree structure. It returns a pointer to the root in a new tree structure that is a copy of the original. Each activation of the COPY procedure has its own instance of the variables IN and OUT.

For additional information about recursive procedures, see the section Entry Data in the chapter Data Types.