In Fibonacci series, each number is the sum of the
two preceding numbers. For example: 0, 1, 1, 2, 3, 5, 8, ….., ∞ (infinity). The
following programs return the nth number entered by user residing in the
Fibonacci series.
Method
1 (Using recursion): Time Complexity: T(n) = T(n-1) + T(n-2) which is
exponential, i.e. this implementation does a lot of repeated work. Extra Space:
O(n) if we consider the function call stack size, otherwise O(1).
#include<stdio.h>
int fib(int n) {
if ( n <= 1 )
return n;
return fib(n-1) + fib(n-2);
}
int main () {
int n ;
printf(" Enter Number to Compute nth Fibonacci
Series: ");
scanf("%d",&n);
printf("\n\n %dth term of Fibonacci Series is
%d\n",n, fib(n));
return 0;
}
Method 2 (Using Dynamic Programming): We can avoid the repeated work done in the method 1 by storing the Fibonacci numbers calculated so far. Time Complexity: O(n), Extra Space: O(n).
#include<stdio.h>
int fib(int n) {
int f[n+1];
int i;
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++) {
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
int main () {
int n ;
printf(" Enter Number to Compute nth Fibonacci
Series: ");
scanf("%d",&n);
printf("\n\n %dth term of Fibonacci Series is
%d\n",n, fib(n));
return 0;
}
Method
3 (Optimizing Method 2): We can optimize the space used in method 2 by
storing the previous two numbers only because that is all we need to get the
next Fibonacci number in series. Time Complexity: O(n), Extra Space: O(1).
#include<stdio.h>
int fib(int n) {
int a = 0, b = 1, c, i;
if( n == 0)
return a;
for (i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
int main () {
int n ;
printf(" Enter Number to Compute nth Fibonacci
Series: ");
scanf("%d",&n);
printf("\n\n %dth term of Fibonacci Series is
%d\n",n, fib(n));
return 0;
}
Method
4 (Using power of the
matrix {{1,1},{1,0}} ): If we
multiply n times the matrix M = {{1,1},{1,0}} to itself (in another words
calculate power(M, n )), then we get the (n+1)th Fibonacci number as the
element at row and column (0, 0) in the resultant matrix. Time Complexity:
O(n), Extra Space: O(1).
#include <stdio.h>
void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);
int fib(int n) {
int F[2][2] = {{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
void multiply(int F[2][2], int M[2][2]) {
int x =
F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y =
F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z =
F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w =
F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
void power(int F[2][2], int n) {
int i;
int M[2][2] = {{1,1},{1,0}};
for (i = 2; i <= n; i++)
multiply(F, M);
}
int main () {
int n ;
printf(" Enter Number to Compute nth Fibonacci
Series: ");
scanf("%d",&n);
printf("\n\n %dth term of Fibonacci Series is
%d\n",n, fib(n));
return 0;
}
Method
5 (Optimizing Method 4): We can do recursive
multiplication to get power(M, n) in the previous method. Time Complexity: O(log
n), Extra Space: O(log n) if we consider the function call stack size,
otherwise O(1).
#include <stdio.h>
void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);
int fib(int n) {
int F[2][2] = {{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
void power(int F[2][2], int n) {
if( n == 0 || n == 1)
return;
int M[2][2] = {{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if (n%2 != 0)
multiply(F, M);
}
void multiply(int F[2][2], int M[2][2]) {
int x =
F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y =
F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z =
F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w =
F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
int main () {
int n ;
printf(" Enter Number to Compute nth Fibonacci
Series: ");
scanf("%d",&n);
printf("\n\n %dth term of Fibonacci Series is
%d\n",n, fib(n));
return 0;
}