Previous Section
 < Free Open Study > 
Next Section


7.10 How Recursion Works

To understand how recursion works and why some programming languages allow it but others do not, we have to take a detour and look at how languages associate places in memory with variable names. The association of a memory address with a variable name is called binding. The point in the compile/execute cycle when binding occurs is called the binding time. We want to stress that binding time refers to a point of time in a process, not the amount of clock time that it takes to bind a variable.

Static storage allocation associates variable names with memory locations at compile time; dynamic storage allocation associates variable names with memory locations at execution time. As we look at how static and dynamic storage allocation work, consider the following question: When are the parameters of a function bound to a particular address in memory? The answer to this question tells us something about whether a language can support recursion.

Static Storage Allocation

As a program is translated, the compiler creates a symbol table. When a variable is declared, it is entered into the symbol table, and a memory location-an address-is assigned to it. As an example, let's see how the compiler would translate the following C++ global declarations:

int girlCount, boyCount, totalKids;

To simplify this discussion, we assume that integers take only one memory location. This statement causes three entries to be made in the symbol table. (The addresses used are arbitrary.)

Symbol

Address

girlCount

0000

boyCount

0001

totalKids

0002

That is, at compile time,

  • girlCount is bound to address 0000.

  • boyCount is bound to address 0001.

  • totalKids is bound to address 0002.

Whenever a variable is used later in the program, the compiler searches the symbol table for its actual address and substitutes that address for the variable name. After all, meaningful variable names are intended for the convenience of the human reader; addresses, however, are meaningful to computers. For example, the assignment statement

totalKids = girlCount + boyCount;

is translated into machine instructions that execute the following actions:

  • Get the contents of address 0000.

  • Add it to the contents of address 0001.

  • Put the result into address 0002.

The object code itself is then stored in a different part of memory. Suppose that the translated instructions begin at address 1000. At the beginning of execution, control is transferred to address 1000. The instruction stored there is executed, then the instruction in address 1001 is executed, and so on.

Where are the parameters of functions stored? With static storage allocation, the formal parameters of a function are assumed to reside in a particular place; for instance, the compiler might set aside space for the parameter values immediately preceding the code for each function. Consider a function with two int parameters, girlCount and boyCount, as well as a local variable, totalKids. Let's assume that the function's code begins at an address called CountKids. The compiler leaves room for the two formal parameters and the local variable at addresses CountKids - 1, CountKids - 2, and CountKids - 3, respectively. Given the function definition

void CountKids(int girlCount, int boyCount)
{
  int totalKids;
  .
  .
}

the statement

totalKids = girlCount + boyCount;

in the body of the function would generate the following actions:

  • Get the contents of address CountKids - 1.

  • Add it to the contents of address CountKids - 2.

  • Store the result in address CountKids - 3.

Figure 7.4 shows how a program with three functions might be arranged in memory.

Click To expand
Figure 7.4: Static allocation of space for a program with three functions

This discussion has been simplified somewhat, because the compiler actually sets aside space not only for the parameters and local variables, but also for the return address (the location in the calling code of the next instruction to process, following the completion of the function) and the computer's current register values. It has, however, drawn attention to the main point: The function's formal parameters and local variables are bound to actual addresses in memory at compile time.

We can compare the static allocation scheme to one way of allocating seats in an auditorium where a lecture will be held. A finite number of invitations are issued for the event, and the exact number of chairs needed are set up before the lecture. Each invited guest has a reserved seat. If anyone brings friends, however, there is nowhere for the invited guests to sit.

What is the implication of binding variable names to memory locations before the program executes? Each parameter and local variable has only a single location assigned to it at compile time. (They are like invited guests with reserved seats.) If each call to a function is an independent event, then no problem arises. But in the case of recursion, each recursive call depends on the state of the values in the previous call. Where is the storage for the multiple versions of the parameters and local variables generated by recursive calls? Because the intermediate values of the parameters and local variables must be retained, the recursive call cannot store its arguments (actual parameters) in the fixed number of locations that were set up at compile time. The values from the previous recursive call would be overwritten and lost. Thus a language that uses only static storage allocation cannot support recursion.

Dynamic Storage Allocation

The situation we have described is also analogous to a class of students that must share one copy of a workbook. Joe writes his exercise answers in the space provided in the workbook, then Mary erases his answers, and writes hers in the same space. This process continues until each student in the class writes his or her answers into the workbook, obliterating all the answers that came before. Obviously, this situation is not practical. What is needed is for each student to read from the single copy of the workbook, then to write his or her answers on a separate piece of paper. In computer terms, each invocation of a function needs its own work space. Dynamic storage allocation provides this solution.

With dynamic storage allocation, variable names are not bound to actual addresses in memory until run time. The compiler references variables not by their actual addresses, but by relative addresses. Of particular interest to us, the compiler references the parameters and local variables of a function relative to some address known at run time, not relative to the location of the function's code.

Activation record (stack frame) A record used at run time to store information about a function call, including the parameters, local variables, register values, and return address

Let's look at a simplified version of how this situation might work in C++. (The actual implementation depends on the particular machine and compiler.) When a function is invoked, it needs space to keep its formal parameters, its local variables, and the return address (the address in the calling code to which the computer returns when the function completes its execution). Just like the students sharing one copy of a workbook, each invocation of a function needs its own work space. This work space is called an activation record or stack frame. A simplified version of an activation record for function Factorial might have the following "declarations":

struct ActivationRecordType
{
  AddressType returnAddr;     // Return address
  int result;                 // Returned value
  int number;                 // Formal parameter
  .
  .
  .
}:

Each call to a function, including recursive calls, generates a new activation record. Within the function, references to the parameters and local variables use the values in the activation record. When the function ends, the activation record is released. How does this happen? Your source code doesn't need to allocate and free activation records; instead, the compiler adds a "prologue" to the beginning of each function and an "epilogue" to the end of each function. Table 7.2 compares the source code for Factorial with a simplified version of the "code" executed at run time. (Of course, the code executed at run time is object code, but we are listing the source code "equivalent" so that it makes sense to the reader.)

Table 7.2: Run-time Version of Factorial (Simplified)

What Your Source Code Says

What the Run-time System Does

int Factorial(int number)
{



  if (number == 0)
    return 1;
  else
    return number *
     Factorial(number - 1);
}

// Function prologue
actRec = new ActivationRecordType;
actRec->returnAddr = retAddr;
actRec->number = number;
// actRec->result is undefined
if (actRec->number == 0)
  actRec->result = 1;
else
  actRec->result =
    actRec->number *
    Factorial(actRec->number-1);
// Function epilogue
returnValue = actRec->result;
retAddr = actRec->returnAddr;
delete actRec;
Jump (goto) retAddr

What happens to the activation record of one function when a second function is invoked? Consider a program whose main function calls Proc1, which then calls Proc2. When the program begins executing, it generates the "main" activation record. (The main function's activation record persists for the entire execution of the program.) At the first function call, an activation record is generated for Proc1: [1]

Click To expand

When Proc2 is called from within Proc1, its activation record is generated. Because Proc1 has not finished executing, its activation record still exists; just like the mathematicians with telephones, one waits "on hold" until the next call is finished:

Click To expand

When Proc2 finishes executing, its activation record is released. But which of the other two activation records becomes the active one-Proc1's or main's? Proc1's activation record should now be active, of course. The order of activation follows the last in, first out rule. We know of a structure that supports LIFO access-the stack-so it should come as no surprise that the structure that keeps track of the activation records at run time is called the run-time stack.

Run-time stack A data structure that keeps track of activation records during the execution of a program

When a function is invoked, its activation record is pushed onto the run-time stack. Each nested level of function calls adds another activation record to the stack. As each function completes its execution, its activation record is popped from the stack. Recursive function calls, like calls to any other functions, generate a new activation record. The level of recursive calls in a program determines how many activation records for this function are pushed onto the run-time stack at any one time.

Using dynamic allocation might be compared to another way of allocating seats in an auditorium where a lecture has been scheduled. A finite number of invitations is issued, but each guest is asked to bring his or her own chair. In addition, each guest can invite an unlimited number of friends, as long as they all bring their own chairs. Of course, if the number of extra guests gets out of hand, the space in the auditorium runs out, and there may not be enough room for any more friends or chairs. Similarly, the level of recursion in a program must eventually be limited by the amount of memory available in the run-time stack.

Let's walk through the function Factorial again, to see how its execution affects the run-time stack. Here is the function:

int Factorial(int number)
{
  if (number == 0)
    return 1;
  else
    return number * Factorial(number - 1);
}

Suppose that the main function is loaded in memory beginning at location 5000, and that the initial call to Factorial is made in a statement at memory location 5200. Suppose also that the Factorial function is loaded in memory at location 1000, with the recursive call made in the statement at location 1010. Figure 7.5 shows a simplified version of how this example program is loaded in memory. (The location numbers have been picked arbitrarily, so that we have actual numbers to show in the return address field of the activation record.)

Click To expand
Figure 7.5: The sample program loaded in memory

When Factorial is called the first time from the statement in the main function at address 5200,

answer = Factorial(4);

an activation record is pushed onto the run-time stack to hold three pieces of data: the return address (5200), the formal parameter number (4), and the value returned from the function (result), which has not yet been evaluated. Rather than showing our activation records as pictures, let's show them as a table. Each new activation record constitutes a new row of the table. The activation record in the last row of the table is now on the top of the run-time stack. We have added a column on the left that identifies which call it is.

Click To expand

The code is now executed. Is number (the number value in the top activation record) equal to 0? No, it is 4, so the else branch is taken:

return number * Factorial(number - 1);

This time the function Factorial is called from a different place-recursively from within the function, from the statement at location 1010. After the value of Factorial (number - 1) is calculated, we want to return to this location to multiply the result times number. A new activation record is pushed onto the run-time stack:

Click To expand

The code for the new invocation of Factorial begins executing. Is number (the number value in the top activation record) equal to 0? No, it is 3, so the else branch is taken:

return number * Factorial(number - 1);

The function Factorial is, therefore, again called recursively from the instruction at location 1010. This process continues until the situation looks as shown below with the fifth call.

Click To expand

As the fifth call is executed, we again ask the question: Is number (the number value in the top activation record) equal to 0? Yes. This time we perform the then clause, storing the value 1 into result (the instance of result in the top activation record, that is). The fifth invocation of the function has executed to completion, and the function returns the value of result in the top activation record. The run-time stack is popped to release the top activation record, leaving the activation record of the fourth call to Factorial at the top of the run-time stack. We don't restart the fourth function call from the beginning, however. As with any function call, we return to the place where the function was called-namely, the return address (location 1010) stored in the activation record.

Next, the returned value (1) is multiplied by the value of number in the top activation record (1) and the result (1) is stored into result (the instance of result in the top activation record, that is). Now the fourth invocation of the function is complete, and the function returns the value of result in the top activation record. Again, the run-time stack is popped to release the top activation record, leaving the activation record of the third call to Factorial at the top of the run-time stack.

Click To expand

We return to the place where we made the recursive call to Factorial.

This process continues until we reach the first call:

Click To expand

At this point, 6 has just been returned as the value of Factorial (number - 1). This value is multiplied by the value of number in the top activation record (that is, 4) and the result, 24, is stored into the result field of the top activation record. This assignment completes the execution of the initial call to the function Factorial. The value of result in the top activation record (24) is returned to the place of the original call (address 5200), and the activation record is popped. This action leaves the main activation record at the top of the run-time stack. The final value of result is stored into the variable answer, and the statement following the original call is executed.

The number of recursive calls constitutes the depth of the recursion. Notice the relationship between the complexity of the iterative version in terms of Big-O notation and the depth of recursion for the factorial: Both are based on the parameter number. Is it a coincidence that the depth of recursion is the same as the complexity of the iterative version? No. Recursion represents another way of doing repetition, so you would expect that the depth of recursion would be approximately the same as the number of iterations for the iterative version of the same problem. In addition, both are based on the size of the problem.

[1]The drawings in this chapter that represent the run-time stack have the top of the stack at the bottom of the picture, because we generally think of memory as being allocated in increasing address order.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)