If you've ever had a programming interview, you're aware that many C programming interviews include a question about writing a program for the Fibonacci sequence. Many people get perplexed by this seemingly basic question. In this article, we'll look at how to use the Fibonacci sequence in C.
What is a Fibonacci Series?
The Fibonacci sequence is a set of numbers that is generated by adding the two numbers before it. Zero and one are the first two terms, respectively. The terms that follow are created by simply adding the two terms before them.
The Fibonacci Series programme may be written in two ways:
- Fibonacci Series without recursion
- Fibonacci Series using recursion
How to Calculate Fibonacci and its Mathematical Representation?
The Fibonacci Sequence or Series is a set of numbers formed by adding two numbers preceding the following number. The Fibonacci numbers are in the integer sequence of 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on.
By combining the two numbers preceding it, the following number is found; 2 is equal to the sum of the two numbers before it (1+1), 3 is equal to the sum of the two numbers before it (1+2), 5 is equal to the sum of the two numbers before it (2+3), and so on.
An example of a Fibonacci sequence is as follows: 0-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1
The first two terms of the series in the previous example are 0 and 1. These two terms are immediately printed. The first two terms are combined to form the third term. Here, since 0 and 1 are the only options, we get 0+1=1. As a result, the third term is written as 1. The second and third terms are used to create the following term, rather than the initial term. It's done till you have the desired quantity of terms or as the user requests. We used eight terms in the above example.
Example
#include<stdio.h>
int main()
{
int first=0, second=1, i, n, sum=0;
printf("Enter the number of terms: ");
scanf("%d",&n);
//accepting the terms
printf("Fibonacci Series:");
for(i=0 ; i<n ; i++)
{
if(i <= 1)
{
sum=i;
}
//to print 0 and 1
else
{
sum=first + second;
first=second;
second=sum;
//to calculate the remaining terms.
//value of first and second changes as a new term is printed.
}
printf(" %d",sum)
}
return 0;
}
Output
In the above program, all variables are first declared. We set the values for the first and second variables first, which will be used to produce further terms. Then we define the term n, which will be used to keep track of the number of terms. To represent the sum of the two digits, we use the term sum. The most recent term is i. It is used in the for loop for iteration. We take the user's number of terms and store it in n. Then, there's a for loop that goes from 0 to the number of phrases the user requested, which is n.
We first have an if statement within the for loop, with the condition verifying if the value of i is smaller than 1. Depending on the number of terms, either zero or one is printed. When there are more than two terms, it is used to print the initial zero and one.
The else component of the loop is executed if the number of terms is more than one. The addition of the variables first and second is assigned to the variable sum in this section. The sum variable is the following phrase. For example, if the first and second values are 0 and 1, the total value will be 1.
How a Program to Calculate Fibonacci Works?
Program on calculation of Fibonacci works on a straight recursive implementation of the aforementioned mathematical recurrence relation.
Example
//Fibonacci Series using Recursion
#include<bits/stdc++.h>
using namespace std;
int fib(int n)
{
if (n <= 2)
return n;
return fib(n4) + fib(n-2);
}
int main ()
{
int n = 7;
cout << fib(n);
getchar();
return 0;
}
Output
The above example shows that this implementation does a lot of repeated work (see the following recursion tree)
Recursion Tree
Fibonacci Series in C Without Recursion
The goto statement is a type of jump statement that is also known as an unconditional jump statement. Within a function, it can be used to hop from one place to another. The steps are as follows:
// C program to print Fibonacci Series
// using goto statement
#include <stdio.h>
// Function to print Fibonacci Number
// using goto statement
void fibUsingGoto(int N)
{
int a = 0, b = 1, sum = 0;
lableFib:
// Print to series first N term
if (N != 0) {
// Print series
printf(" %d", a);
// Create next term
sum = a + b;
a = b;
b = sum;
// Decrement N
N--;
// Jump to lableFib
goto lableFib;
}
}
// Driver Code
int main()
{
// Given number N
int N = 10;
// Function Call
fibUsingGoto(N);
return 0;
}
Output
Fibonacci Series in C Using Recursion
Declare three variables as 0, 1, and 0 accordingly for a, b, and total. With the first term, second term, and the current sum of the Fibonacci sequence, use the fib() method repeatedly. After the main function calls the fib() function, the fib() function calls itself until the Fibonacci Series N values are computed. In each recursive call, update the values of a, b, and total as shown below:
// C program to print fibonacci
// series using recursion
#include <stdio.h>
// Recursive function to print
// Fibonacci series
void fib(int a, int b, int sum, int N)
{
// Print first N term of the series
if (N != 0) {
printf(" %d", a);
sum = a + b;
a = b;
b = sum;
// Decrement N
N--;
// recursive call function fib
fib(a, b, sum, N);
}
}
// Driver Code
int main()
{
// Given Number N
int N = 10;
// First term as 0
// Second term as 1 and
// Sum of first and second term
fib(0, 1, 0, N);
return 0;
}
Output
Conclusion
Learning about the Fibonacci sequence gives a programmer an understanding on how to solve certain problems that require a solution from a base case. This is also the reason why it is so famous and relevant in the programming world. Want to learn more about such interesting concepts and sharpen your programming skills by learning more advanced topics?
Enroll in Simplilearn’s Post Graduate Program in Full Stack Web Development, to get more grasp on concepts like these with our well curated videos and practical examples. This certification course provides training in almost 30 programming languages and tools and will help you get the mastery in multiple development skills required to become a full-stack developer and land an opportunity to work for the biggest companies in the software development world.