Subroutine - Local Variables, Recursion and Reentrancy

Local Variables, Recursion and Reentrancy

A subprogram may find it useful to make use of a certain amount of scratch space; that is, memory used during the execution of that subprogram to hold intermediate results. Variables stored in this scratch space are termed local variables, and the scratch space is termed an activation record. An activation record typically has a return address that tells it where to pass control back to when the subprogram finishes.

A subprogram may have any number and nature of call sites. If recursion is supported, a subprogram may even call itself, causing its execution to suspend while another nested execution of the same subprogram occurs. Recursion is a useful means to simplify some complex algorithms, and breaking down complex problems. Recursive languages generally provide a new copy of local variables on each call. If the programmer desires the value of local variables to stay the same between calls, they can be declared static in some languages, or global values or common areas can be used. Here is an example of recursive subroutine in C/C++ to find Fibonacci numbers:

int fib(int n) { if(n<=1) return n; return fib(n-1)+fib(n-2); }

Early languages like Fortran did not initially support recursion because variables were statically allocated, as well as the location for the return address. Most computers before the late 1960s such as the PDP-8 did not have support for hardware stack registers.

Modern languages after ALGOL such as PL/1 and C almost invariably use a stack, usually supported by most modern computer instruction sets to provide a fresh activation record for every execution of a subprogram. That way, the nested execution is free to modify its local variables without concern for the effect on other suspended executions in progress. As nested calls accumulate, a call stack structure is formed, consisting of one activation record for each suspended subprogram. In fact, this stack structure is virtually ubiquitous, and so activation records are commonly termed stack frames.

Some languages such as Pascal and Ada also support nested subroutines, which are subroutines callable only within the scope of an outer (parent) subroutine. Inner subroutines have access to the local variables of the outer subroutine that called them. This is accomplished by storing extra context information within the activation record, also termed a display.

If a subprogram can function properly even when called while another execution is already in progress, that subprogram is said to be reentrant. A recursive subprogram must be reentrant. Reentrant subprograms are also useful in multi-threaded situations, since multiple threads can call the same subprogram without fear of interfering with each other. In the IBM CICS transaction processing system, quasi-reentrant was a slightly less restrictive, but similar, requirement for application programs that were shared by many threads.

In a multi-threaded environment, there is generally more than one stack. An environment that fully supports coroutines or lazy evaluation may use data structures other than stacks to store their activation records.