In nonrecursive programs, references to global and to static variables always refer to the current actual storage assigned to them. Hence any changes to their values during execution of the program will be reflected back in their values. Local automatic variables are treated differently. Local copies are made, and these are referred to during the execution of the function to which they are local. If the local variables are automatic, the storage for the local copies disappears when the function terminates or returns. If the local variables are static, the storage remains after the function is terminated, and the variable retains its value for the next time the function is called.
This situation holds for recursion also. Each recursive call to a function produces its own copies of automatic local variables. Thus there may be many different values for the same local variable?/FONT>each applicable to its own invocation of the function. As with nonrecursion, there is only one storage allocation for a global or a static variable, and it holds the last value of the variable.
Parameters passed in the argument lists of functions are treated as variables local to the function. They are passed by value. New storage is established for each parameter. The storage is initially set to the value of the corresponding actual parameter when the function is invoked. In effect, this storage represents a local copy of the actual parameter. Any reference in the function is interpreted as a reference to the local copy only. This implies that any change to a parameter during the execution of the function will not be reflected back to the storage used for the actual parameter; it can not have its value changed by the function.
The only way to change the original value of a variable used as a parameter is to pass the address of the parameter instead of its value. This is done automatically in the case of arrays and character strings. When an array is passed as a parameter, the address of the first storage location in the array is passed. This negates the need to make local copies of all the values of the array in the function and thus waste memory. Addresses for parameters can also be passed as pointers A copy is made in the function and is local to the function. Using the pointer, the value of the parameter can be changed.
Here is a simple example.
Suppose that simple is invoked with actual parameters a and b, containing 0 and 1 respectively. It is invoked by the statement, simple (a,&b). Within the function, x initially has a copy of a as its value?/FONT>0 in this case. y refers to the storage for b?/FONT>that is, y is a pointer to the storage for b. The first statement of simple causes x to assume the value l, the second statement causes the storage for b to contain 2, and the third statement sets the storage for b to 3. When the calling program continues, a will still be 0, but b will be 3.
Parameters of recursive programs are treated in just this way. Any time cursive call is made within a recursive program, the recursive call acts just like a call to any function. The only difference is that, since a recursive function may generate many recursive calls during its execution, many local copies of its parameters may be produced. References to a parameter by value during the execution of each recursive call will then mean the current local copy of that parameter. Reference to a parameter passed by a pointer to it always means the same actual parameter.
In the recursive version of copy, note that
n Null and rest are local variables of the initial call to copy and remain local variables in all subsequent recursive calls. Local copies of null and rest are thus made on any call to copy.
n First is passed by value and second by pointer.
n Whenever copy is executing and generates a recursive call to copy(next(first),&rest), the actual first parameter of copy is the current copy of next(first)?/FONT>i.e., the copy associated with the currently executing call to copy. Any references to the first parameter during the generated recursive call refer to the new local copy associated with that call.
When first points to the list as shown in Figure 4.3, and copy(first, second) is executed, the sequence of events and memory configurations that will take place appear in Figure 4.4. First0, first1, first2, first3 refer to the local copies of the actual first parameter associated with the initial, first, second, and third recursive calls to copy, respectively. Similarly for the other variables. A question mark indicates an as yet undefined value. Be sure you understand Figure 4.4 and how it represents the execution of copy.
An alternative version of copy that returns a pointer to the copy of the list first would be as shown on page 160.
This version differs from the original version in two ways. One, it has only one parameter, the list to be copied, and two, it returns a pointer to the new copy rather than setting a second parameter to point to the new copy.
simple (x,py)
int x, *py;
{x = 1;
*py = 2;
*py = x + *py;
}
Figure 4.3 The List for COPY to Process
(a) The Situation after SETINF0 (*PSECOND, FIRST0)
(b) After SETINF0(REST1, FIRST1)
(c) After SETINF0(REST2, FIRST 2)
(d) After REST2:= NULL 3; i.e., SECOND:= NULL
(e) After SETLINK(REST1, REST2)
(f) After SETLINK(REST0, REST1)
Figure 4.4 Simulation of COPY(FIRST,&SECOND)
listpointer copy(first)
/* Returns a pointer to the first record of a new list which is a
copy of the list first.
*/
listpointer first;
{listpointer null,second,setnull(),avail(),next();
null = setnull();
if (first == null)
second = null;
else
{second = avail();
setinfo(second,first);
setlink(second,copy(next(first)));
}
return (second);
}