Home Back to 370 Assembler Tips & Tricks Index Links

Writing Recursive Routines

  • Recursive subroutines are routines that are able to call themselves from somewhere within themselves.  For some reason, people, generally programming students, find the concept difficult - especially in assembler language.

  • In actuality, the concept and coding technique is quite simple.

  • Recursive subroutines are useful in designing parsers, compilers, translators, interpreters and complex mathematical functions.

  • There are only a few simple considerations to designing recursive routines.  The routine must be fully re-entrant and it must have a standard way of exiting to the caller (itself or a higher level caller).

  • From force of habit, I always code a linkage stack for use in any subroutine I write.  This is the first step in designing a recursive subroutine.

  • For simple routines, you may allocate a static stack from real memory, but for more complex routines, it might be necessary to allocate a dynamic stack that can grow or shrink as required.  I'll typically design a dynamic linkage stack using a linked list.

  • One of the most important considerations is to prevent stack overflow (i.e., exceeding the capacity of the stack).

  • Another of the most important considerations is to code an exit from the recursion.  Failure to do this properly will end up in an endless loop and stack overflow or storage allocation failure in the case of a dynamic stack.

  • The following is a code "snippet" for a simple recursive subroutine without stack checking or a dynamic stack:


RECURSE  CSECT                     CSECT Definition.
RECURSE  AMODE 31                  31-Bit Addressing.
RECURSE  RMODE ANY                 Any Residency.
         ENTRY RECEP               Entry point.
           .
           .
           .
RECEP    DS    0H                  CSECT Entry.
           .
           .                       Allocate save area storage...
           .                       ...for re-entrancy.
           .
         STORAGE OBTAIN,           Allocate storage for stack.         C
               LENGTH=STACKL,      Size of storage to allocate.        C
               LOC=ANY,            Any (31/24 Bit) storage location.   C
               COND=YES            We'll handle any exceptions.
         LTR   R15,R15             Successfull allocation?
         BNZ   FAIL                Take branch if not.
         LR    R8,R1               Load A(Allocated storage).
           .
           .
           .
         L     R15,=A(RERTN)       Load A(Recursive Routine).
         BALR  R14,R15             Call Recursive Routine first time.
           .
           .
           .
         STORAGE RELEASE,          De-allocate stack storage.         C
               LENGTH=STACKL,      Size of storage to de-allocate.    C
               ADDR=(R8)           Address of storage to de-allocate.
           .
           .
           .
         L     R14,RSAR14          Some return address save area.
           .
           .                       Free any other allocated storage.
           .
         XR    R15,R15             Clear return code.
         BR    R14                 Return to caller.
         EJECT
*--------------------------------------------------------------------*
*        RERTN - Recursive Subroutine.                               *
*--------------------------------------------------------------------*
         SPACE ,
RERTN    DS    0H                  Recursive routine entry point.
         ST    R14,0(,R8)          Store return address to stack.
         LA    R8,4(,R8)           Increment stack pointer.
           .
           .
           .
         BNE   RERTN10             Some condition to start recursion.
         OI    GETOUT,X'80'        Set the "get out" switch.
RERTN10  DS    0H                  Recursion begins.
           .
           .
           .
         TM    GETOUT,X'80'        Some kind of "get out" switch.
         BO    RERTN99             Exit this recursion.
         BAL   R14,RERTN           Call ourself.
RERTN99  DS    0H                  Routine exit.
         SH    R8,=H'4'            Decrement stack pointer.
         L     R14,0(,R8)          Restore return address.
         BR    R14                 Return to caller.
         SPACE ,
*--------------------------------------------------------------------*
         EJECT
           .
           .
           .
         END   ,                   End of module.

I will continue to add tips and techniques as time permits.

Please direct any inquiries or problems regarding this web to webmaster@marcsweb.com

Page design, composition and HTML by Marc Niegowski
Copyright © 1998-2012, Marc Niegowski - Connectivity, Inc., All Rights Reserved
23 W. Fourth Street • Media • Pennsylvania • 19063-2805 • USA
Phone: 610-566-0227 • Fax: 610-566-0641 • Email: Marc@Tech-Center.com

Revision Date: Wednesday, November 15, 2006 10:03:31 AM