Design and Analysis of Algorithms - 2

Implement functions to print n^th Fibonacci number using iteration and recursive method. Compare the performance of two methods by counting number of steps executed on various inputs. Also draw a comparative chart.

Code:

 

#include<stdio.h>

 

int count_ite=0;

int count_rec=0;

void febo_ite(int );

int febo_rec(int );

 

int main()

{

    int n,ans;

    printf("Enter position of number: ");

    scanf("%d",&n);

    febo_ite(n);

    ans=febo_rec(n);

    printf("Using Recursion: %d th number is = %d\n",n,ans);

    printf("No of Steps= %d\n\n",count_rec);

}

 

void febo_ite(int n)

{

    count_ite++;

    int next,i, first=0,second=1;

    count_ite++;

    if(n==0)

    {

        count_ite++;

        next=0;

    }

    else if(n==1)

    {

        count_ite++;

        next=1;

    }

    else

    {

        count_ite++;

        for(i=1;i<n;i++)

        {

            count_ite++;

            next=first+second;

            count_ite++;

            first=second;

            count_ite++;

            second=next;

        }

    }

    printf("\n Using Iteration: %d th number is = %d\n",n,next);

    printf("No of Steps= %d\n\n",count_ite);

}

 

int febo_rec(int n)

{

    count_ite++;

    if(n==0)

    {

        count_rec++;

        return 0;

    }

    else if(n==1)

    {

        count_rec++;

        return 1;

    }

    else

    {

        count_rec++;

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

    }

}

 

Output:

 

 

 

 

 

Analysis Table

 Analysis Chart

 

 

 

 

 

 

Conclusion:

 

In this Practical We Conclude that in the starting both Recursion and iteration Method takes less steps but when the value increases there is strict change or increment of steps in Recursion Method as compared to the Iteration Method.

 So that we can conclude that Iteration Method is fast and more efficient than Recursion Method in finding number position in Fibonacci Series.