**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:

**F _{n} = F_{n-1} + F_{n-2}**

Where, F_{n} denotes the nth term of Fibonacci series.

The first two terms of this series are considered to be:

F_{0} = 0 (Zeroth term of Fibonacci sequence)

F_{1} = 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 :

F_{2} = F_{1} + F_{0} = 0 + 1 = 1

F_{3} = F_{2} + F_{1} = 1 + 1 = 2

F_{4} = F_{3} + F_{2} = 2 + 1 = 3

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

Write a C Program that generates fibonacci series.

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.

- Fibonacci Series Program in C (While Loop)
- C Program to Print First n Terms of Fibonacci Sequence using For Loop
- Fibonacci Series in C using Recusrion
- Fibonacci Series in C using Command Line Argument
- Fibonacci Series in C using Dynamic Programming

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

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.

/* * 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; } }

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).

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

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

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

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; }

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).

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

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

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.

`/*`

`* C Program to print Fibonacci series using recursion`

`*/`

`#include <stdio.h>`

`#include <stdio.h>`

void fib(int N, int fib1, int fib2)

`{`

if (N == 0)

`{`

return;

`}`

printf("%d\n", fib1+fib2);

fib(N-1, fib2, fib1+fib2);

return;

`}`

void main()

`{`

int N;

printf("Enter value of N: ");

scanf("%d", &N);

printf("Fibonacci Series is ...\n");

if(N == 1)

`{`

printf( "0\n");

`}`

else if( N == 2 )

`{`

printf( "0\n1\n");

`}`

`else`

`{`

printf( "0\n1\n");

fib( N-2, 0, 1);

`}`

return;

`}`

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(2 ^{N})**

The time complexity of fibanocci series is O(2

^{N}) 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.

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

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

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"); }

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.

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

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**.

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.

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]); } }

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(2^{N}).

**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.

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

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.

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]); } }

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(2^{N}).

**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.

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.

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(2^{N}).

**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.

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]**

**Related Posts:**

- Apply for C Internship
- Practice Computer Science MCQs
- Watch Advanced C Programming Videos
- Check C Books
- Practice BCA MCQs