### 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.
Output:
•           34
•  The output consist of Nth Fibonacci number.

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:

#include <iostream>
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);
}

Complexity:
Time Complexity: The above program will take O(2n) because of equation T(n) = T(n-1) + T(n-2) which is exponential.

Space Complexity: The space complexity for the above program is O(n) because of implementation of recursion on stack.

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.

Program:

#include <iostream>
#include <vector>
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);
}

Complexity:
Time Complexity: The above program will take O(n) time.

Space Complexity: The space complexity for the above program is O(n) for storing computed values.

Method 3: (Iterative Solution)
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:

#include <iostream>
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);
}

Complexity:
Time Complexity: The above program will take O(n) time.

Space Complexity: The space complexity for the above program is O(1) because we are storing only previous two terms.

Please write on comment section if you find any mistake or for any suggestions.

#### More Articles of Abhishek Kumar Singh:

Name Views Likes
C++ boost::range::replace_if 956 0
C++ boost::range::copy_backward 724 1
C++ boost::range::max_element 1177 0
C++ boost::range::inplace_merge 647 0
C++ boost::range::copy 1250 1
C++ boost::algorithm::is_partitioned() 819 1
C++ boost::algorithm::copy_if() 967 0
C++ boost::range::for_each (version 2) 727 0
C++ boost::range::set_symmetric_difference 636 0
C++ boost::remove_copy_if 723 0
C++ boost::range::set_intersection 940 0
C++ boost::range::find_end 673 0
C++ boost::range::remove_erase_if 1480 0
C++ boost::range::push_back 1086 0
C++ boost::range::generate 624 0
C++ boost::algorithm::any_of() 625 0
C++ boost::range::insert 696 0
C++ boost::range::remove_erase 896 0
C++ boost::range::reverse 1165 0
C++ boost::algorithm::equal() 724 1
C++ boost::range::copy_n 804 0
C++ boost::range::random_shuffle 1218 1
C++ boost::algorithm::partition_point() 586 0
C++ boost::algorithm::one_of_equal() 508 0
C++ boost::algorithm::all_of() 857 1
C++ boost::range::merge 962 0
C++ boost::range::reverse_copy 733 0
C++ boost::range::find 716 0
C++ boost::range::fill_n 586 0
Removing duplicate elements from std::vector (using std::unique and std::set) 2125 1
C++ boost::range::equal 671 0
C++ boost::algorithm::iota() 904 0
C++ boost::range::is_sorted 819 0
test article 760 2
C++ boost::algorithm::is_permutation() 808 1
C++ boost::partial_sum 831 0
C++ boost::range::partial_sort 893 1
C++ boost::range::min_element 989 0
C++ boost::range::iota 990 0
C++ boost::range::set_union 687 0
C++ boost::algorithm::partition_copy() 1047 3
C++ boost::range::swap_ranges 592 0
C++ boost::range::for_each 857 0
C++ boost::range::upper_bound 1021 0
C++ boost::range::binary_search 1187 0
C++ boost::algorithm::all_of_equal() 528 0
C++ boost::algorithm::copy_n() 647 1
C++ boost::range::lower_bound 985 0
C++ boost::algorithm::gather() 1388 0
C++ boost::algorithm::none_of_equal() 570 0
C++ boost::algorithm::one_of() 688 2
C++ boost::range::rotate 817 0
C++ boost::algorithm::any_of_equal() 817 0
Use of Comparator in C++ 2045 0
C++ boost::range::count 785 0
C++ boost::range::replace_copy_if 610 0
C++ boost::range::remove 789 2
C++ boost::remove_if 1360 1
C++ boost::range::nth_element 1095 1
C++ boost::range::partition 715 1
C++ boost::range::erase 607 0
C++ boost::range::fill 873 1
C++ boost::range::find_if 1214 0
C++ boost::range::lexicographical_compare 781 0
C++ boost::algorithm::none_of() 559 0
C++ boost::algorithm::hex() 3330 0
C++ boost::range::replace 702 0
C++ boost::range::replace_copy 794 1
C++ boost::range::set_difference 903 0
C++ boost::range::overwrite 680 0
C++ boost::range::count_if 908 0
C++ boost::range::push_front 641 0
C++ boost::range::includes 638 0
C++ boost::algorithm::is_sorted() 667 0
C++ boost::range::remove_copy 595 1
C++ boost::algorithm::minmax_element 596 1
Deletion of leaf node of a Binary Search Tree 1653 1
Nth Fibonacci Number (Recursive Solution, Dynamic Programming, Iterative Solution 3768 1
C++ boost::range::rotate_copy 621 0