# nth Fibonacci number in C++

Written by

Garvit Gulati

## Program to find Nth Fibonacci Number in C++

Given an n, we have to write a program that calculates the Nth term of the Fibonacci series and prints it.

### Fibonacci series

Fibonacci series is a sequence of numbers in which each number is the sum of previous two numbers. Mathematically, if F(n) denotes the nth term of the Fibonacci series, then

F(n)=F(n-1)+F(n-2)

Fibonacci series: 1,1,2,3,5,8,13……

Fibonacci series appears in variety of computer algorithm such as Fibonacci search technique and the Fibonacci heap data structure and graphs such as Fibonacci Cubes.

### Recursion

Recursion is a method of solving a problem whereby a function calls itself directly or indirectly.

It is very useful in solving problems like tower of Hanoi, factorial and even the current question.

While writing the recursive solution, we don’t think about the complete solution but just think about calculating the answer if we had the and to or two smaller steps.

A recursive function contains two parts:

– Stopping condition:

It is the call for which the function returns a value and doesn’t call itself again. It is very essential as otherwise the function will keep calling itself and we will end up with an infinite loop.

– Recursive part:

Here, the function calls itself to find the solution.

### # Algorithm

1. Write a function that returns nth term of the Fibonacci series.
2. If n is less than or equal to 1(either 0 or 1) then return n.
3. If not call the function for n-1 and n-2 and return their sum.

Code

#include <iostream>
using namespace std;
int fib(int n)
{
if (n <= 1)	//stopping condition
return n;

else	//recursive part

return (fib(n - 1) + fib(n - 2));

}
int main()
{
int n;
cout &lt;&lt; "Enter the term which you want to calculate\n";

cin &gt;&gt; n;

}
Enter the term which you want to calculate
Answer:21