Page 77 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes x = s.top;

s.top = x-1;
return (s.data[x]);
}
}
void push(struct stack *s, double e)
{
if(s.top == MAXC)
printf(“Stack full!”);
else
{
s.top = s.top + 1;
s.data[s.top] = e;
}
}
int empty(struct stack *p)
{
if(s.top == -1)
return 1;
else
return 0;
}
3.3.2 Simulating Recursive Function using Stack

A recursive solution to a problem is often more expensive than a non-recursive solution, both in
terms of time and space. Frequently, this expense is a small price to pay for the logical simplicity
and self-documentation of the recursive solution. However, in a production program (such as
a compiler, for example) that may be run thousands of times, the recurrent expense is a heavy
burden on the system’s limited resources.
Thus, a program may be designed to incorporate a recursive solution in order to reduce the expense

of design and certification, and then carefully converted to a non-recursive version to be put into
actual day-to-day use. As we shall see, in performing such as conversion it is often possible to
identify parts of the implementation of recursion that are superfluous in a particular application

and thereby significantly reduce the amount of work that the program must perform.
Suppose that we have the statement

rout (x); where route is defined as a function by the header
rout(a); x is referred to as an argument (of the calling function), and a is referred to as a parameter
(of the called function).

What happens when a function is called? The action of calling a function may be divided into
three parts:
1. Passing Arguments

2. Allocating and initializing local variables
3. Transferring control to the function.

72 LOVELY PROFESSIONAL UNIVERSITY