Fibonacci series are the numbers in the following integer sequence
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ....
the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent term is the sum of the previous two terms. In mathematical terms, the Nth term of Fibonacci numbers is defined by the recurrence relation.
fibonacci(N) = fibonacci(N - 1) + fibonacci(N - 2);
whereas, fibonacci(0) = 0 and fibonacci(1) = 1
Interesting facts
- If you take any two successive (one after the other) Fibonacci Numbers, their ratio is very close to the Golden Ratio which is approximately 1.618034.
- The bigger the pair of Fibonacci Numbers, the closer the approximation.
C program to print fibonacci series till N terms
In this program we first take number of terms in fibonacci series as input from user. Then starting with 0 and 1 as first two terms of the fibonacci series we generate and print consecutive fibonacci numbers by adding last two terms using a for loop.
#include <stdio.h>
int main(){
int terms, lastNumber=1,secondLast=0;
int currentNumber=0,counter;
printf("Enter number of terms in Fibonacci series: ");
scanf("%d", &terms);
for(counter = 0; counter < terms; counter++){
if(counter < 2){
currentNumber = counter;
} else {
currentNumber = lastNumber + secondLast;
secondLast = lastNumber;
lastNumber = currentNumber;
}
printf("%d ", currentNumber);
}
return 0;
}
Output
Enter number of terms in Fibonacci series: 8 0 1 1 2 3 5 8 13
C Program to generate fibonacci series till Nth term and store it in array
In this program we use an array to store fibonacci series generated till now. Every fibonacci number is equal to the sum of values in last two indexes of fibonacci array.
fibonacciArray[N] = fibonacciArray[N - 1] + fibonacciArray[N - 2];
#include <stdio.h>
int main(){
int terms, fibonacciArray[100] = {0}, counter;
printf("Enter number of terms in Fibonacci series: ");
scanf("%d", &terms);
for(counter = 0; counter < terms; counter++){
if(counter < 2){
fibonacciArray[counter] = counter;
} else {
fibonacciArray[counter] = fibonacciArray[counter - 1]
+ fibonacciArray[counter - 2];
}
printf("%d ", fibonacciArray[counter]);
}
return 0;
}
Output
Enter number of terms in Fibonacci series: 10 0 1 1 2 3 5 8 13 21 34
C program to print fibonacci series using recursion
This program uses recursion to calculate Nth fibonacci number, fibonacci(N) returns Nth fibonacci number by recursively calling fibonacci(N - 1) and fibonacci(N - 2). fibonacci(N) function does lots of repeated work by recalculating lower terns again and again.
For example:
fibonacci(5) = fibonacci(4) + fibonacci(3);
It calculates value of 3rd and 4th term of fibonacci series to get 5th term.
fibonacci(6) = fibonacci(5) + fibonacci(4);
Now, while calculating 6th term, it again calculate 5th and 4th term which we already calculated while generating 5th term.
We can solve this problem of recalculating already calculated terms by storing all previous terms in an array. This approach is called recursion with memorization(Dynamic Programming).
#include <stdio.h>
int fibonacci(int term);
int main(){
int terms, counter;
printf("Enter number of terms in Fibonacci series: ");
scanf("%d", &terms);
for(counter = 0; counter < terms; counter++){
printf("%d ", fibonacci(counter));
}
return 0;
}
int fibonacci(int term){
/* Exit condition of recursion*/
if(term < 2)
return term;
return fibonacci(term -1) + fibonacci(term - 2);
}
Output
Enter number of terms in Fibonacci series: 9 0 1 1 2 3 5 8 13 21Related Topics