Recent Posts

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.

Read more at: https://en.wikipedia.org/wiki/Fibonacci_number

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.

Read more about recursion

# 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 << "Enter the term which you want to calculate\n";
    cin >> n;
    cout << "Answer:" << fib(n);
}

Output

Enter the term which you want to calculate
8

Answer:21
nth Fibonacci number in C++