c++ program to find nth fibonacci number | c++ programs

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
        

Read my other posts

• CPP program to find the area of a triangle
• Program to find the dot and cross product
• CPP Program to find the steps in order to attack enemies
• program to implement a 3D vector and 3X3 matrix struct in c/c++
• C++ Program to Find Factorial using recursion