Fibonacci Series Program in C

What is Fibonacci Series in C?

Fibonacci series are the numbers in the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21….. The series in the Fibonacci sequence is equal to the sum of the previous two terms. The Fibonacci sequence’s first two terms are 0 and 1 respectively.

Mathematically, we can denote it as:

Fn = Fn-1 + Fn-2

Where, Fn denotes the nth term of Fibonacci series.

The first two terms of this series are considered to be:
F0 = 0 (Zeroth term of Fibonacci sequence)
F1 = 1 (First term of Fibonacci sequence)

Now, by using the above two values we can easily calculate all other terms of Fibonacci series as follows :

advertisement
advertisement

F2 = F1 + F0 = 0 + 1 = 1
F3 = F2 + F1 = 1 + 1 = 2
F4 = F3 + F2 = 2 + 1 = 3

Hence, the series continue as follows 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……

Problem Description

Write a C Program that generates fibonacci series.

Problem Solution

In fibonacci series the first two numbers in the Fibonacci sequence are 0 and 1 and each subsequent number is the sum of the previous two.

There are several ways to print fibonacci series in C language. Let’s take a detailed look at all the approaches to display fibonacci series in C.

Method 1: Fibonacci Series Program in C using While Loop

In this method, we use a while loop to generate n fibonacci series.

Program/Source Code

Here is source code of the C program to generate fibonacci series. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

There are several ways to print fibonacci series in C language. Let’s take a detailed look at all the approaches to display fibonacci series in C.

advertisement
/*
 * C program to generate Fibonacci Series. Fibonacci Series
 * is 0 1 1 2 3 5 8 13 21 ...
 */
 
#include <stdio.h>
 
void main()
{
    int  fib1 = 0, fib2 = 1, fib3, limit, count = 0;
 
    printf("Enter the limit to generate the Fibonacci Series \n");
    scanf("%d", &limit);
    printf("Fibonacci Series is ...\n");
    printf("%d\n", fib1);
    printf("%d\n", fib2);
    count = 2;
    while (count < limit)
    {
        fib3 = fib1 + fib2;
        count++;
        printf("%d\n", fib3);
        fib1 = fib2;
        fib2 = fib3;
    }
}
Program Explanation

1. In this C program, we are reading the limit to generate the Fibonacci series using limit variable.
2. In Fibonacci series the first two numbers in the Fibonacci sequence are 0 and 1 and each subsequent number is the sum of the previous two.
3. For example Fibonacci series is 0, 1, 1, 2, 3, 5, 8, 13, 21…………
4. Initially assign the value of ‘fib1’ variable as 0, the value of ‘fib2’ variable as 1 and the value of ‘count’ variable as 2.
5. While loop is used to check the condition that the value of ‘count’ variable is less than the value of ‘limit’ variable.
6. If the condition is true then execute the loop. Compute the value of ‘fib1’ variable and the value of ‘fib2’ variable then assign the value to ‘fib3’ variable.
7. Increment the value of ‘count’ variable by 1. Assign the value of ‘fib2’ variable to ‘fib1’ variable and the value of ‘fib3’ variable to ‘fib2’ variable.
8. Print the Fibonacci series using printf statement.

Time Complexity: O(N)
The time complexity of fibanocci series is O(N) for iterative approach as we are printing N terms.

Space Complexity: O(1)
As we have not used any extra space, therefore constant space is used i.e O(1).

Runtime Test Cases

In this case, entering “6” as the limit generate the fibonacci series.

advertisement
Enter the limit to generate the Fibonacci Series
6
Fibonacci Series is ...
0
1
1
2
3
5

Method 2: Fibonacci Series Program in C using For Loop

In this method, we use a for loop to generate n fibonacci series.

Program/Source Code

Here is source code of the C program to generate fibonacci series using for loop. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C program to generate Fibonacci Series using for loop
 */
 
#include <stdio.h>
int main()
{
    printf("Enter the number of terms of Fibonacci series \n");
    int limit;
    scanf("%d", &limit);
    int firstTerm=0,secondTerm=1;
    printf("First %d terms of Fibonacci series are : ",limit);
    if(limit>=1)
    {  
        // Printing the first term
        printf("%d ",firstTerm);
    }
    if(limit>=2)
    {  
        //  Printing the second term
        printf("%d ",secondTerm);
    }
 
    // Using the first two term to print the following terms of series
    int prevTerm = secondTerm,prevToPrevTerm = firstTerm;
    for(int i=3;i<=limit;i++)
    {
        int ithTerm=prevTerm+prevToPrevTerm; // F(i) = F(i-1) + F(i-2)
        printf("%d ",ithTerm);
 
        // Assigning (i-1)th term to prevToPrevterm for the next iteration
        prevToPrevTerm = prevTerm;
 
        // Assigning ith term to prevTerm for the next iteration
        prevTerm = ithTerm;   
    }
    return 0;
}
Program Explanation

1. Take the number N upto which we have to find the fibonacci sequence using limit variable.
2. If limit is greater than or equal to 1 then print the first term.
3. If limit is greater than or equal to 2 then print the second term.
4. Use the first two term to print the following terms of series using for loop.
5. Calculate the ith term using ithTerm=prevTerm+prevToPrevTerm;
6. Assign the (i-1)th term to prevToPrevterm for the next iteration.
7. Assign ith term to prevTerm for the next iteration.
8. Repeat the process untill the condition is false. Once its failed print the Fibonacci series using printf statement.

Time Complexity: O(N)
The time complexity of fibanocci series is O(N) for iterative approach as we are printing N terms.

Space Complexity: O(1)
As we have not used any extra space, therefore constant space is used i.e O(1).

Runtime Test Cases

In this case, entering “8” as the limit generate the fibonacci series.

Enter the limit to generate the Fibonacci Series
8
Fibonacci Series is ...
0
1
1
2
3
5
8
13

Method 3: Fibonacci Series in C using Recusrion

In this method, we use a recusrion to generate n fibonacci series.

Program/Source Code

Here is source code of the C program to generate fibonacci series using recursion. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to print Fibonacci series using recursion
  3.  */
  4.  
  5. #include <stdio.h>
  6. #include <stdio.h>
  7.  
  8. void fib(int N, int fib1, int fib2)
  9. {
  10.     if (N == 0)
  11.     {
  12.         return;
  13.     }
  14.     printf("%d\n", fib1+fib2);
  15.  
  16.     fib(N-1, fib2, fib1+fib2);
  17.     return;
  18. }
  19.  
  20. void main()
  21. {
  22.     int N;
  23.     printf("Enter value of N: ");
  24.     scanf("%d", &N);
  25.     printf("Fibonacci Series is ...\n");
  26.     if(N == 1)
  27.     {
  28.         printf( "0\n");
  29.     }
  30.     else if( N == 2 )
  31.     {
  32.         printf( "0\n1\n");
  33.     }
  34.     else
  35.     {
  36.         printf( "0\n1\n");
  37.  
  38.         fib( N-2, 0, 1);
  39.     }
  40.     return;
  41. }
Program Explanation

1. Define a function `fib` with input as integer variables N, fib1 and fib2 and return nothing/void. End function if N is equal to 0, else print sum of fib1 and fib2 then recursively call `fib` with input N-1, fib2 and fib1 + fib2.
2. Take the number N upto which we have to find the fibonacci sequence.
3. If N is 1 print 1 and if N is 2 print 0 and 1 else go to step 4.
4. Call the `fib` function with input as N-2, 0 and 1.
5. End of the program.

Time Complexity: O(2N)
The time complexity of fibanocci series is O(2N) for recursive approach as we are printing N terms.

Space Complexity: O(N)
The space complexity of fibanocci series is O(N) for recursive approach as function is recursively called N-2 times and stack memory is used.

Runtime Test Cases

In this case, entering “10” as the limit generate the fibonacci series.

Enter value of N: 10
Fibonacci Series is ...
0
1
1
2
3
5
8
13
21
34

Method 4: Fibonacci Series in C using Command-Llne Argument

In this method, we are computing first N Fibonacci numbers using command line arguments.

Program/Source Code

Here is source code of the C Program to generate fibonacci series of n numbers using command-Llne argument. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*  
 * C Program to Generate Fibonacci Series of N Numbers using 
 * Command-Line Argument
 */
 
#include <stdio.h>
 
void main(int argc, char * argv[])
{
    int n, last = 0, prev = 1, curr, cnt;
    n = atoi(argv[1]);
    printf("Printing first %d fibonacci nos. -> ", n);
    printf("%d ", last);
    printf("%d ", prev);
    cnt = 2;
    while (cnt< = n-1)
    {
        curr = last + prev;
        last = prev;
        prev = curr;
        cnt++;
        printf("%d ", curr);
    }
    printf("\n");
}
Program Explanation

In this C program, we are computing first N Fibonacci numbers using command line arguments. The arguments argc and *argv[] are used. Initially assign the first variable value as 0 and second variable value as 1.

The rec_fibonacci() function is used to compute the Fibonacci series. If condition statement is used to check the value of ‘num’ variable is equal to 2. If the condition is true then exit the function. Print the statement as the first two numbers are already printed.

If the condition is false then execute the else statement. Compute the value of ‘first’ and ‘second’ variable. Assign to third variable and print the Fibonacci series. Then the value of ‘second’ variable is assigned to the value of ‘first’ variable and the value of ‘third’ variable is assigned to ‘second’ variable and decrement the value of ‘num’ variable.

Runtime Test Cases
 
$ gcc arg5.c
$ a.out 10
Printing first 10 fibonacci nos. -> 0 1 1 2 3 5 8 13 21 34

Fibonacci Series in C using Dynamic Programming

Whenever recursive functions for fibonacci series are called, this recursion tree forms.

As soon as f(N) is called for the first time, its value is stored. In subsequent calls for f(N), we use the precalculated value for further calculations. A significant reduction in computation time can be achieved as a result of this.

Dynamic programming works by storing the result of subproblems so that when their solutions are required, they are at hand and we do not need to recalculate them. This technique of storing the value of subproblems is called memoization.

Method 5: Fibonacci Series in C using Memoization

In the memoization approach, when we recursively calculate a fibonacci number, we first check if it has already been calculated. If it has been calculated, we do not recursively calculate it.

Program/Source Code

Here is source code of the C Program to generate fibonacci series using memoization. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*  
 * Fibonacci Series in C using Memoization
 */
 
#include <stdio.h>
// Recursive Function to get n fibonacci numbers
int get_fibonacci(int a[],int n)
{
    if(n==1)
        return a[n-1]=0;
    if(n==2)
        return a[n-1]=1;
 
    // Check the presence of Nth fibonacci number
    // If present then return it
    if(a[n-1]!=-1)
        return a[n-1];
 
    // else calculate Nth fibonacci number and store in the array
    else
        return a[n-1]=get_fibonacci(a,n-1)+get_fibonacci(a,n-2);
}
int main()
{
    int limit;
    printf("Enter the limit to generate the Fibonacci Series \n");
    scanf("%d", &limit);
    if(limit <= 0)
    printf("Enter the size of fibonacci series and the size should be greater than zero");
    printf("Fibonacci Series is ...\n");
 
    // array to store fibonacci numbers
    int a[limit];
    for(int i=0;i<limit;i++)
    a[i]=-1;
 
    // function to store fibonacci numbers
    get_fibonacci(a,limit);
 
    // Printing fibonacci numbers
    for(int i=0;i<limit;i++)
    {
        printf("%d\n", a[i]);
    }
}
Program Explanation

1. Take the number N upto which we have to find the fibonacci sequence using limit variable.
2. Create a recursive function “get_fibonacci” to get n fibonacci numbers.
3. Next, look for the presence of the Nth Fibonacci number. If it is present, return it; Otherwise, calculate the Nth Fibonacci number and store it in the array using return a[n-1]=get_fibonacci(a,n-1)+get_fibonacci(a,n-2);
4. Use the array to store fibonacci numbers.
5. Print the Fibonacci series using printf statement.

Time Complexity: O(N)
Since, each node is called exactly once therefore time complexity reduces to O(N) from O(2N).

Space Complexity: O(N)
The space complexity of fibanocci series is O(N) for memoization approach as function is recursively called N-2 times and stack memory is used.

Runtime Test Cases

In this case, enter “7” as the limit to generate the fibonacci series.

Enter the limit to generate the Fibonacci Series 
7
Fibonacci Series is ...
0
1
1
2
3
5
8

Method 6: Fibonacci Series in C using Tabulation

The bottom-up dynamic approach consists of combining the results of smaller problems to solve
a bigger problem. Here we solve problem with smallest possible input and then use this result to
solve bigger problems until we get solution of entire problem.

Program/Source Code

Here is source code of the C Program to generate fibonacci series using tabulation. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*  
 * Fibonacci Series in C using Tabulation
 */
 
#include <stdio.h>
int main()
{
    int limit;
    printf("Enter the limit to generate the Fibonacci Series \n");
    scanf("%d", &limit);
    if(limit <= 0)
    printf("Enter the size of fibonacci series and the size should be greater than zero");
    printf("Fibonacci Series is ...\n");
    // array to store fibonacci numbers
    int a[limit];
 
    // 1st and 2nd fibonacci number
    a[0]=0;
    a[1]=1;
    // Calculate the Nth fibonacci number with N-1 and N-2 number
    if(limit>2)
    {
        for(int i=2;i<limit;i++)
        a[i]=a[i-1]+a[i-2];
    }
    for(int i=0;i<limit;i++)
    {
        printf("%d\n", a[i]);
    }
}
Program Explanation

1. Take the number N upto which we have to find the fibonacci sequence using limit variable.
2. a[0]=0; and a[1]=1; is the 1st and 2nd fibonacci number.
3. Calculate the Nth fibonacci number with N-1 and N-2 number.
4. Print the Fibonacci series using printf statement.

Time Complexity: O(N)
Since, each node is called exactly once therefore time complexity reduces to O(N) from O(2N).

Space Complexity: O(N)
The space complexity of fibanocci series is O(N) for tabulation approach as function is recursively called N-2 times and stack memory is used.

Runtime Test Cases

In this case, enter “5” as the limit to generate the fibonacci series.

Enter the limit to generate the Fibonacci Series 
5
Fibonacci Series is ...
0
1
1
2
3

We can do further optimization in the above bottom up approach.

When we only need (N-1)th and (N-2)th fibonacci number to calculate Nth fibonacci number, there is no need to store all the fibonacci numbers from the start.

We just need two variables to store previous two fibonacci numbers and we can then compute
next number of the series.

Program/Source Code

Here is source code of the C Program to generate fibonacci series using bottom up approach. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*  
 * Fibonacci Series in C using Bottom Up Approach
 */
 
#include <stdio.h>
void main()
{
    // First 2 fibonacci numbers
    int fib1 = 0;
    int fib2 = 1;
    int fib3, limit, count = 0;
    printf("Enter the limit to generate the Fibonacci Series \n");
    scanf("%d", &limit);
    printf("Fibonacci Series is ...\n");
    if(limit==1)
    {
        printf("%d\n", fib1);
        return;
    }
    else if(limit==2)
    {
        printf("%d\n", fib1);
        printf("%d\n", fib2);
        return;
    }
    else
    {
        count = 2;
        printf("%d\n", fib1);
        printf("%d\n", fib2);
        while (count < limit)
        {
            fib3 = fib1 + fib2;
            count++;
            printf("%d\n", fib3);
            fib1 = fib2;
            fib2 = fib3;
        }
        return ;
    }
}

Time Complexity: O(N)
Since, each node is called exactly once therefore time complexity reduces to O(N) from O(2N).

Space Complexity: O(1)
The space complexity of fibanocci series is O(1) for bottomup approach. As we have not used any extra space, therefore constant space is used.

Runtime Test Cases

In this case, enter “10” as the limit to generate the fibonacci series.

Enter the limit to generate the Fibonacci Series 
10
Fibonacci Series is ...
0
1
1
2
3
5
8
13
21
34

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.