What is the Fibonacci series and how to program it in C++?
Fibonacci sequence
By definition, the first two elements of the Fibonacci sequence are 0 and 1
and each next element is the sum of the previous two elements.
Fibonacci sequence for n -1 elements
0 1 1 2 3 5 8 13 ....
The nth element fn of the sequence can be defined as
fn = f(n - 1) + f (n - 2 ) when n > 1.
c++ program to find nth fibonacci number - using recursion
#include <iostream>
using namespace std;
int fib(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return fibo(n - 1) + fibo(n - 2);
}
int main()
{
cout<< "Enter the value of N to get nth element of the sequence: "<< endl;
int n;
cin >> n;
cout<< n<< " th element: "<< fibo(n);
}
Program output
Enter the value of N to get nth element of the sequence:
10
10 th element: 55
This program is not efficient to calculate the nth element for the
bigger values of n. if n = 90 you will never get the answer because you'll never wait for
that.
Don't rely on recursion, here
Recursion is best to solve other recursive problems but for this, we shouldn't rely on it. It is too slow and does the same job more than once.
To understand why is that so, see the below tree structure of recursive
calls which actually shows you how our program works under the hood.
Now You can pretty much understand. fib(n - 3) invoked more than once.
And it does the extra efforts to get the result.
Rewriting the program
c++ program to find nth fibonacci number
#include < iostream >
int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int a = 0;
int strong = 1;
int c = 0;
for (int em = 2; !(em > n); em ++) {
c = a + strong;
a = strong;
strong = c;
}
return c;
}
int main() {
std::cout<< "Enter the value of N to get nth element of the sequence: "<<
std::endl;
int n;
std::cin >> n;
std::cout<<; n<<; " th element: "<<; fib(n);
return 0;
}
Program Output
Enter the value of N to get nth element of the sequence:
10
10 th element: 55
