Fibonacci Series Using Recursion in C refers to a number series. The Fibonacci series is created by adding the preceding two numbers ahead in the series. Zero and one are the first two numbers in a Fibonacci series. We generate the rest of the numbers by adding both the previous numbers in the series.
In this article, we will take a look at the Fibonacci series using recursion in C and its uses according to the GATE Syllabus for CSE (Computer Science Engineering). Read ahead to learn more.
Table of Contents
- What is the Fibonacci Series in C?
- How to Write the Fibonacci series in C Language?
- Calculation of Fibonacci Series in C
- Practice Problems on Fibonacci Series Using Recursion in C
- FAQs
What is the Fibonacci Series in C?
In a Fibonacci number series, the next number in line is basically the sum of the last two numbers (preceding numbers). The first two numbers are always 1 and 0 in the series. Thus, it goes like 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, etc.
How to Write the Fibonacci Series in C Language?
We can write this series in a C program using two of the major ways:
- Using Recursion
- Without Recursion
In this article, we will take a look at how we can write the Fibonacci series in the C programs with the use of recursion.
Calculation of Fibonacci Series in C
As we know, the Fibonacci series basically goes like a series of various numbers like 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Thus, the next number in this series will be found when we add up both the numbers occurring before it. Here is how it is calculated here:
- The number 2 is calculated when we add both the numbers preceding it, i.e., 1+1.
- The number 3 is calculated when we add both the numbers preceding it, i.e., 2+3, and so on in the series.
In the series, the first two numbers are 0 and 1. Thus, these two values will be directly printed in the output. Then, the third value will be created after we add these first two terms, 0 and 1. Thus, we will get 0+1 = 1. Thus, the program will print the value 1 as the third term. After this, the program will generate the fourth value by adding the third and the second ones and not by adding the first one. Thus, in this case, the term generated would be 1+1 = 2. It will be continually done by the C program until the total number of terms that we requested is generated in the output.
Thus, a Fibonacci series will grow like this:
0
1
0+1 = 1
1+1 = 2
1+2 = 3
2+3 = 5
3+5 = 8
5+8 = 13
and so on …
Generating Fibonacci Series Using the Recursion Method in C Language
Here, we have displayed how we can make use of the recursion method for generating a Fibonacci series in the C programs. In this case, the calling of the Fibonacci function will occur recursively unless the program generates a proper output. Firstly, in the function, the program checks if the available number m in the program is one or zero. If yes, then the program will return the value m. If not, then the Fibonacci will be called recursively with the values m-1 and m-2.
Let us take a look at the program,
#include<stdio.h>
void printFibonacci(int m){
static int m1=0,m2=1,m3;
if(m>0){
m3 = m1 + m2;
m1 = m2;
m2 = m3;
printf(“%d “,m3);
printFibonacci(m-1);
}
}
int main(){
int m;
printf(“Please enter your preferred number of elements here: “);
scanf(“%d”,&m);
printf(“The Fibonacci Series will be: “);
printf(“%d %d “,0,1);
printFibonacci(m-2); //We have used m-2 because we have 2 numbers already printed here
return 0;
}
The output obtained out of the code mentioned above would be:
Please enter your preferred number of elements here: 15
The Fibonacci Series will be:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
Recursion Using for Loop in Fibonacci Series
#include<stdio.h>
#include<conio.h>
int recursivefibonacci(int);
int main(){
int m, x;
printf(“Please enter the total number of values you want in the Fibonacci series : \n”);
scanf(“%d”,&m);
printf(“The Fibonacci series of these numbers would be equal to : \n”);
for(x=0;x<m;x++) {
printf(“%d “,recursivefibonacci(x));
}
getch();
}
int recursivefibonacci(int x){
if(x==0) return 0;
else if(x==1) return 1;
else return (recursivefibonacci(x-1) + recursivefibonacci(x-2));
}
The output obtained out of the code mentioned above would be:
Please enter the total number of values you want in the Fibonacci series :
6
The Fibonacci series of these numbers would be equal to :
0 1 1 2 3 5
Explanation:
- In the code mentioned above, we have first declared a function with the name recursivefibonacci. It will basically take an integer in the form of the input, and then return an integer element as well in the output.
- The variables that we have used in the program are m and x. Both of these are of the integer data types.
- Here, our main logic will begin wherever the for loop is. The program will call this loop m number of times, and m is also given here as an input by the user.
- Every time the loop condition satisfies the given value of m, the value of x will pass in the form of a parameter to the recursivefibonacci(x) method in the form of the input.
- The program consists of the nested if-else in the recursivefibonacci(x) body.
- In case the input in the program is 1, it will then return 1.
- In case the input in the program is 0, it will then return 0.
- When the value given to us happens to be greater than 1, then we will perform the calculation with recursivefibonacci(x-1) + recursivefibonacci(x-2).
Practice Problems on Fibonacci Series Using Recursion in C
Take a look at the following program, and find the output for different sets of inputs:
#include <stdio.h>
int main(void) {
int m, x=0, y=1, z;
printf(“Please enter the total number of terms in the program : \n”);
scanf(“%d”,&m);
if(m==1){
printf(“%d”, x);
} else if(m == 2)
{ printf(“%d %d”, x, y);
} else
{ printf(“%d %d “, x, y);
for(int p=3; p<=m; p++){
printf(“%d “, RecursiveTerm(p));
}
}
return 0;
}
int RecursiveTerm(int m){
if(m==1)
return 0;
else if(m==2)
return 1;
return RecursiveTerm(m-2) + RecursiveTerm(m-1);
}
The output of the following inputs would be:
1. Input: m= 8
Answer: Please enter the total number of terms in the program :
8
0 1 1 2 3 5 8 13
2. Input: m= 10
Answer: Please enter the total number of terms in the program :
10
0 1 1 2 3 5 8 13 21 34
3. Input: m= 3
Answer: Please enter the total number of terms in the program :
3
0 1 1
4. Input: m= 15
Answer: Please enter the total number of terms in the program :
15
0 1 1 2 3 5 8 13 21 34 55 89 144 233
Frequently Asked Questions
Is zero (0) considered a Fibonacci number?
Yes, zero is the very first number in a Fibonacci series by default. Thus, we consider it as a Fibonacci number.
What’s the easiest way to understand and calculate the Fibonacci series in the C language?
In a Fibonacci number series, the next number in line is basically the sum of the last two numbers (preceding numbers). The first two numbers are always 1 and 0 in the series. Thus, it goes like 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, etc.
Do we specify the total number of terms that we want in the Fibonacci series output?
Yes, we have to. Let us look at the following program:
#include
int f(int);
int main()
{
int m, a= 0, y;
printf(“Please enter the total number of terms in the program : m”);
scanf(“%d”, &m);
printf(“The Fibonacci series terms will be equal to : m”);
for(y = 1; i <= m; y++)
{
printf(“%dn”, printfibonacci(a));
a++;
}
return 0;
}
int printfibonacci(int m)
{
if(m == 0 || m == 1)
return m;
else
return(printfibonacci(m-1) + printfibonacci(m-2));
}
Here, we input the total number of terms we want in the form of output in the variable m. For instance, this input is 7, then the output generated out of this program would be:
Please enter the total number of terms in the program :
9
The Fibonacci series terms will be equal to :
0 1 1 2 3 5 8 13 21
Is there any disadvantage of using the recursive method in calculating the Fibonacci series in C?
Yes. There is one major disadvantage of generating the Fibonacci series using recursion in C. Recursion involves calling a function repeatedly in a program that may eventually lead to stack overflow if we try to calculate some larger terms in the Fibonacci series.
We can avoid this. We can use Memoization. It is the process in which we store the Fibonacci series calculated in the array and then use it for lookup. This way, the recursive algorithm’s running time gets reduced a lot. It is very important to do, as this series has a wide application in the field of Computer Science as well as Mathematics.
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.
Also Explore,
Comments