Nth Fibonacci Number (Recursive Solution, Dynamic Programming, Iterative Solution
Description:
In this article we shall use various methods for finding Nth Fibonacci Number.
Example:
Input: 9
The first line of input is Nth term.
Method 1: (Recursive Solution)
Consider the example of finding Nth term of Fibonacci series. Below is the Fibonacci series:
1, 1, 2, 3, 5, 8, 13, 21
The first two terms of both 1, and each subsequent term is sum of previous two terms. Recursive definition of
Fibonacci number is
Fibonacci ( 1 ) = Fibonacci ( 2 ) = 1 if n = 1, 2
Fibonacci ( n ) = Fibonacci ( n - 1 ) + Fibonacci ( n - 2 ) for n > 2
The simplest recursive algorithm to compute Nth term of Fibonacci is direct translation of mathematical
definition:
Program:
using namespace std;
long long fib(int n)
{
if(n == 1 || n == 2)
return 1;
return fib(n - 1) + fib(n - 2);
}
int main()
{
int n;
cin >> n;
cout << fib(n);
}
1, 1, 2, 3, 5, 8, 13, 21
The first two terms of both 1, and each subsequent term is sum of previous two terms. Recursive definition of
Fibonacci number is
Fibonacci ( 1 ) = Fibonacci ( 2 ) = 1 if n = 1, 2
Fibonacci ( n ) = Fibonacci ( n - 1 ) + Fibonacci ( n - 2 ) for n > 2
The simplest recursive algorithm to compute Nth term of Fibonacci is direct translation of mathematical
definition:
Program:
using namespace std;
long long fib(int n)
{
if(n == 1 || n == 2)
return 1;
return fib(n - 1) + fib(n - 2);
}
int main()
{
int n;
cin >> n;
cout << fib(n);
}
Method 2: (Dynamic Programming)
In our recursive method when we compute 20th term of Fibonacci then fib(3) is called 2584 times and fib(10) is
called 89 times. It means that we are computing the 10th term of Fibonacci 89 times from scratch.
In the ideal world, if we have already computed value of fib(10) once, we should not be recomputing it again.
Memoization, Dynamix Programming are techniques used to solve this problem more efficiently. This can be
achieved by storing the computed values in an array, and using them later when called.
called 89 times. It means that we are computing the 10th term of Fibonacci 89 times from scratch.
In the ideal world, if we have already computed value of fib(10) once, we should not be recomputing it again.
Memoization, Dynamix Programming are techniques used to solve this problem more efficiently. This can be
achieved by storing the computed values in an array, and using them later when called.
Program:
using namespace std;
long long fib(int n, vector<long long> &dp)
{
if(n == 1 || n == 2)
return 1;
if(dp[n] != 0) // Checking if Nth term is already computed or not
return dp[n];
return dp[n] = fib(n-1, dp)+fib(n-2, dp); // Storing the computed values
}
int main()
{
int n;
cin >> n;
vector<long long> dp(101); // Creating the array for storing computed values
cout << fib(n, dp);
}
This method is pretty straightforward, we shall iteratively compute each value sequentially and store the
previous two numbers only, because previous two numbers will get us the next Fibonacci number in series.
Program:
using namespace std;
long long fib(int n)
{
long long a = 1, b = 1, c;
if(n == 1 || n == 2)
return 1;
for(int i = 3; i < n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
int main()
{
int n;
cin >> n;
cout << fib(n);
}
previous two numbers only, because previous two numbers will get us the next Fibonacci number in series.
Program:
using namespace std;
long long fib(int n)
{
long long a = 1, b = 1, c;
if(n == 1 || n == 2)
return 1;
for(int i = 3; i < n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
int main()
{
int n;
cin >> n;
cout << fib(n);
}
Comments