Fibonacci Series Program In C: A simple introduction

In the Fibonacci series, each number is the sum of the two previous numbers. The first two numbers in the Fibonacci series are 0 and 1.

The sequence Fn of Fibonacci numbers is defined by the recurrence relation:

Fn = Fn-1 + Fn-2

with seed values

F0 = 0 and F1 = 1.

So if n =7, the Fibonacci series can look like this:

F7 = 0 1 1 2 3 5 8

Methods to get the nth Fibonacci number:

 

Recursive way to find an nth Fibonacci number.

 

#include<stdio.h>

int Fibonacci( int n)
{
    if(n < 0)  //check positive number
        return -1;
    else if ( n == 0 )
        return 0;
    else if ( n == 1 )
        return 1;
    else
        return ( Fibonacci(n - 1) + Fibonacci(n - 2) );
}

int main()
{
    int n = 0, fibnumber = 0;

    printf("\n Enter Number to find nth Fibonacci Number =  ");
    scanf("%d", &n);

    fibnumber = Fibonacci(n);
    if(fibnumber < 0)
    {
        printf("Please Enter Positive number\n\n");
    }
    else
    {
        printf("\n %d Fibonacci Number = %d\n\n", n, fibnumber);
    }

    return 0;
}

Output:

 

Code Analysis

• If (n < 0) – check whether the given number is +ve or not. If it is TRUE, the function will return an error message.
• If (n== 0) – check whether the given number is 0 or not. If it is TRUE, the function will return Zero.
• If (Number == 1) – check the specified number is equal to 1 or not. If it is TRUE, the function will return One.
• If the number is greater than 1, then the recursive operation is performed.

Time Complexity: T(n) = T(n-1) + T(n-2) .

You can observe the recursion tree that this implementation does a lot of repeated work. So it is not a good way to find the nth Fibonacci number.

               fib(5)   
                     /                  
               fib(4)                fib(3)   
             /                      /     
         fib(3)      fib(2)         fib(2)    fib(1)
        /             /           /      
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    
fib(1) fib(0)

 

 

Optimize way to find an nth Fibonacci number

 

#include<stdio.h>

int Fibonacci(int n)
{
    int f0 = 0, f1 = 1, f =0, i=0;
    if( n == 0)
        return f0;
    for (i = 2; i <= n; i++)
    {
        f = f0 + f1;
        f0 = f1;
        f1 = f;
    }
    return f1;
}

int main ()
{
    int n = 0;
    int fn = 0;

    printf("\n Enter Number to find nth Fibonacci Number =  ");
    scanf("%d", &n);

    if(n < 0)
    {
        printf("Please Enter Positive number\n\n");
        return -1;
    }

    fn =  Fibonacci(n);
    printf("\n %d Fibonacci Number = %d\n\n", n, fn);

    return 0;
}

 

In the above code, simply we are using the concept Fn = Fn-1 + Fn-2 .

Recommended Posts for you:

Reference: Fibonacci  series in C