Design and Analysis of Algorithms

190 Design and Analysis of Algorithms

while(i <= n){

f = f*i;

i++;

}

return f;

}

We leave further reduction by C style and the transformation using ET and RE to the students.

Example 3

The Fibonacci series is defi ned by the recurrence relation:

fi b(n) = n if n = 0 or n = 1

= fi b(n – 2) + fi b(n – 1) if n > 1

First, the recursive implementation is:

int rfib(int n){

if( n == 0 || n == 1)

return n;

else

return rfib(n-2) + rfib(n-1);

}

Using the steps 1 to 5 given in Example 1.

the base statement is: if( n == 0 || n == 1) return (n);

the recursion control variable is n → i

the loop control condition is ...