Page 78 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 3: Stacks

Let us examine each of these three steps in turn. Notes

1. Passing arguments: For a parameter in C, a copy of the argument is made locally within the
function, and any changes to the parameter are made to that local copy. The effect to this
scheme is that the original input argument cannot be altered. In this method, storage for
the argument is allocated within the data area of the function.
2. Allocating and initializing local variables: After arguments have been passed, the local
variables of the function are allocated. These local variables include all those declared
directly in the function and any temporaries that must be created during the course of
execution.

3. Transferring control to the function: At this point control may still not be passed to
the function because provision has not yet been made for saving the return address. If
a function is given control, it must eventually restore control to the calling routine by
means of a branch. However, it cannot execute that branch unless it knows the location
to which it must return. Since this location is within the calling routine and not within the
function, the only way that the function can know this address is to have it passed as an

argument. This is exactly what happens. Aside from the explicit arguments specified by the
programmer, there is also a set of implicit arguments that contain information necessary
for the function to execute and return correctly. Chief among these implicit arguments is
the return address. The function stores this address within its own data area. When it is
ready to return control to the calling program, the function retrieves the return address and
branches to that location. Once the arguments and the return address have been passed,
control may be transferred to the function, since everything required has been done to
ensure that the function can operate on the appropriate data and then return to the calling
routine safely.

Return from a Function

When a function returns, three actions are performed. First, the return address is retrieved and
stored in a safe location. Second, the function’s data area is freed. This data area contains all local
variables (including local copies of arguments), temporaries, and the return address. Finally, a
branch is taken to the return address, which had been previously saved. This restores control to
the calling routine at the point immediately following the instruction that initiated the call. In
addition, if the function returns a value, that value is placed in a secure location from which the
calling program may retrieve it. Usually this location is a hardware register that is set-aside for
this purpose.

Task Discuss maze problem.

3.3.3 Simulation of Factorial

Let us look at the factorial function as a recursion example. We present the code for that function,
including temporary variables explicitly and omitting the test for negative input, as follows:
int fact(int n)
{
int x, y;
if (n == 0) return(l);
x = n-l;
y = fact(x);

LOVELY PROFESSIONAL UNIVERSITY 73