Page 179 - DCAP407_DATA_STRUCTURE

Data Structure

Time_for is the running time for the parts of the algorithm. The Time_for depends on the input data size
for the computed recursive function.
Therefore, the recurrence relation is as given below:

T (n) = Time_for (Preprocess, n) + Time_for (Divide, n) + Time_for (Combine, n) + T(n1) + …. + T (nk).
Where, n1 to nk is less than n.

If a recursive algorithm takes ‘c’ steps and decreases the parameter by 1, then
we may express the running time as a function, i.e., time (N). Here, time (N)
represents the running time on N number of input elements.
time (N) = c + time (N-1)
If N =1, then time (1) = c
This equation is easy to solve and the solution is as follows:
time (N) = c + time (N-1)
c + c + time (N-2)

= c + c + … + time (1)
= c + c + … + c (N times)
= c * N
9.5 Iteration vs. Recursion

Let us study iteration and recursion. They are applied to a program as per the situation. Table 9.2
discusses the difference between iteration and recursion.

Table 9.2: Iteration vs. Recursion

Iteration Recursion

Uses repetitive structures like for, Uses selection structures like if, if else
while or do while loop and uses them or switch statement and achieves
explicitly. repetition with the help of repeated
function calls.

The body loop terminates when the The body loop terminates when the
termination condition fails. Each time base condition is satisfied. The base
control passes into the loop, the condition is achieved by invoking the
counter is updated. same function. Every time the function
is invoked, a simple version of the
original problem is obtained until base
condition is achieved.
Example:
int factorial (int n) Example:
{ int factorial (int n)
int j, prod = 1; {
for (j = 0; j < n; j++) If (n==0)
prod = prod * j; return 1;
return prod; else
}
return (n*factorial(n-1));
}
In the example program, int factorial Contd..
(int n), the function prototype is In the example program, int factorial

172 LOVELY PROFESSIONAL UNIVERSITY