New update is available. Click here to update.

Fibonacci series in C++

Kushleen Waraich
Last Updated: Nov 22, 2022
Difficulty Level :
EASY
fibonacci series in c++

Introduction

How does the Fibonacci series work?

The Fibonacci sequence is a sequence in which each number is the sum of the preceding two numbers. The first two numbers of a Fibonacci series are 0 and 1. 

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the function, 

  Fn = Fn-1 + Fn-2

With initial two terms values as,

  F0 = 0 and F1 = 1

The fibonacci series starts with like this 

0,1,1,2,3,5,8,13,21,........

There are different approaches to finding Fibonacci numbers:

  • Without Using Recursion
  • Using Recursion
  • Using Memoization
  • Using Dynamic Programming
  • Space-optimized Using Loops
  • Using Matrix Multiplication
  • Using Formula
     

We will discuss each approach with a detailed explanation.

Fibonacci Series in C++ Without Using Recursion

First, two pre-defined variables, t1 and t2, are assigned values 0 and 1, respectively. 

Then a for loop will run for the input no.(n) of time. The new number is printed in the loop by adding two numbers before, and the series continues.

#include <bits/stdc++.h>
using namespace std;


int main()
 {
    int i, n, t1 = 0, t2 = 1, nT;
    cin>>n;


    for (i = 1; i <= n; ++i) {
        cout<<t1<<" ";
        nT = t1 + t2;
        t1 = t2;
        t2 = nT;
  }

  return 0;

Fibonacci Series in C++ Using Recursion

First, we will declare a function fibonacci() which will calculate the Fibonacci number at position n. If n equals 0 or 1, it returns n. Otherwise, the function recursively calls itself and returns fibonacci(n-1) + fibonacci(n-2);

This C++ Program demonstrates the computation of Fibonacci Numbers using Recursion.

#include <bits/stdc++.h>
using namespace std;
//recursive function for fibonacci
int fibonacci(int n)
{
    //if n is zero or one return the number
    if(n<=1)
    {
        return n;
    }
    //recursive call to n-1 and n-2 
    return fibonacci(n-1)+fibonacci(n-2);

}
int main()
{
  int n;
  n=10;
  cout<<fibonacci(n);
}


Time Complexity: O(2^n), which is exponential. 

The recurrence relation for the above code is 

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

Space Complexity: O(n) if we consider the function call stack space because the maximum function call at a given time is n which is the left branch of the recursion tree.

Using Memoization

We can reduce the complexity of the program to a huge extent by using memoization. By making repetitive calls into functions earlier, we were increasing the time complexity of our code.

This can be improved if we make the recursive call again, but this time we will store the value for each recursive call in an array, thus ensuring that we are doing the whole recursive calculation for a value only once. Below is the Memoization implementation of the program for Fibonacci numbers.


#include <bits/stdc++.h>
using namespace std;
#define N 1000
int dp[N];
int fibonacci(int n)
{
    // we will make a call if an element in array dp is -1
    if(dp[n]==-1)
    {   
        if(n<=1)
        {
            dp[n]=n;
        }
        else
        {
            //call to n-1  and n-2
            dp[n]=fibonacci(n-1)+fibonacci(n-2);
        }
    }
    return dp[n];
}

int main(){

    int n;
    n=10;
    // initializing values of an array to -1
memset(dp,-1,sizeof(dp));
    cout<<fibonacci(n);
}


Time Complexity: O(n) as we make calls for value from 1 to n only once.

Space complexity: O(n) as we use an array to store values of recursive calls

Using Dynamic Programming

In Dynamic Programming, we will add the previous two numbers to get the following term and repeat it until we get the nth term. For this, we will create an array and store the values of an element in it. We will use a loop to sum up, the previous elements to get the final Fibonacci element. Below is the program for Fibonacci numbers using the Dynamic Programming approach.

#include <bits/stdc++.h>
using namespace std;

int fibonacci(int n)
{
    // dp[] for storing values of Fibonacci numbers
    int dp[n+1];
    // initialize zeroth and first element
    dp[0]=0;
    dp[1]=1;

    for(int i=2;i<=n;i++)
    {
        // add previous two numbers to get the next term in series
        dp[i]=dp[i-1]+dp[i-2];
    }

    return dp[n];
}

int main(){

    int n;
    n=10;
    
    cout<<fibonacci(n);
}


Time Complexity: O(n)

Space Complexity: O(n), due to the use of an array of size n to store values.

Space-optimized Using Loops

We can optimize the space used in the above program as we only need the nth element from the array. We can keep track of the last two elements and keep on updating them as we progress. Below is the implementation of the space-optimized approach.

#include <bits/stdc++.h>
using namespace std;

int fibonacci(int n)
{
    // initialize prev1 and prev2 to keep track of previous two elements
    int prev1=0;
    int prev2=1;

    int res;
    for(int i=2;i<=n;i++)
    {
        // add previous two numbers to get the next term in series
        res=prev1+prev2;
        prev1=prev2;
        prev2=res;
    }

    return res;
}

int main(){

    int n;
    n=10;
    
    cout<<fibonacci(n);
}

Using Matrix Multiplication

In this method, we will multiply the matrix {{1,1},{1,0}} with itself n times, then the first element, i.e., the element at (0,0), will give (n+1)th Fibonacci number. 

Using Matrix Multiplication

We will use matrix multiplication and will be multiplying the 2X2 matrix. Suppose we have the following two matrices.
 

Using Matrix Multiplication

After multiplication, we will put the result in another matrix C.

matrix c

Now to find the fourth Fibonacci number, we need to calculate the cube of the Matrix. To calculate the cube of the Matrix, we will multiply the array by itself and then multiply the resultant Matrix with the original Matrix again.

Multiplying Matrix with itself

Fibonacci number

 

Multiplying the resultant matrix from the above step with the original Matrix
 

Original Matrix in Fibonacci Number

 

The first element of the resultant matrix gives us the 4th Fibonacci number, 3.

We will be using this result to multiply the matrix in our code.

#include <bits/stdc++.h>
using namespace std;
// power function to multiply the array
void power(int fib[2][2],int n)
{
    int arr[2][2]={{1,1},{1,0}};

  for(int i=2;i<n;i++)
  {
    // multiply elements of the matrix 
    int a=fib[0][0]*arr[0][0]+fib[0][1]*arr[1][0];
    int b=fib[0][0]*arr[0][1]+fib[0][1]*arr[1][1];
    int c=fib[1][0]*arr[0][0]+fib[1][1]*arr[1][0];
    int d=fib[1][0]*arr[0][1]+fib[1][1]*arr[1][1];
    
    // updating the values in fib[] array
    fib[0][0]=a;
    fib[0][1]=b;
    fib[1][0]=c;
    fib[1][1]=d;
  }

}
int fibonacci(int n)
{
    // initializing the Matrix
    int fib[2][2]={{1,1},{1,0}};
    if(n<=1)
    {
        return n;
    }
    power(fib,n);

    return fib[0][0];
}

int main(){
    int n;
    n=10;
cout<<fibonacci(n);
}


Time Complexity: O(n)

Space Complexity: O(1)

Using Formula in Fibonacci Series

We can find the nth term of the Fibonacci series using the following formula.

Fn = {[(√5 + 1)/2]n} / √5

#include <bits/stdc++.h>
using namespace std;

int fibonacci(int n)
{

    double res = (1 + sqrt(5)) / 2;
    return round(pow(res, n) / sqrt(5));

}

int main ()
{
    int n = 10; 
    cout << fibonacci(n)<<endl;
    return 0;
}


Time Complexity: O(logn), because calculating res^n takes log(n) time.

Space Complexity: O(1)

Frequently Asked Questions

What is the Fibonacci Series program? 

The Fibonacci program is to generate the Fibonacci series, which is a series in which each number is the sum of the preceding two numbers. The first two numbers of a Fibonacci sequence are 0 and 1.

What are the first 20 Fibonacci numbers? 

0,1,1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, and 6765 are the first twenty Fibonacci numbers.

What is fibonacci series in C++?

The Fibonacci sequence is a series where the next term is the sum of the previous two terms. The first two terms of the Fibonacci sequence are 0, followed by 1. We can write a simple C++ program to compute the Fibonacci series up to a given number.

How do you make a Fibonacci sequence in C++?

We can create the Fibonacci sequence in C++ using various approaches such as recursion, loops, matrix multiplication, etc. If they are space constraints, the Fibonacci sequence can be generated using recursion with memoization or using the matrix multiplication technique. In recursion, we can provide a base case and build the solution upwards.

How do you find the nth Fibonacci number in C ++?

We can find the nth Fibonacci number using a simple while loop. Initialize two variables, n1 and n2, with 0 and 1, respectively. Create a third variable answer to hold the nth Fibonacci number. Now do the following:

for(int i=1;i≤n-2;i++) {
    answer = n1 + n2;
    n1 = n2;
    n2 = answer;
}
if(n == 1){
    cout<<n1<<endl;
}
else if (n == 2){
    cout<<n2<<endl;
}
else{
    cout<<answer<<endl;
}

Conclusion

This article discusses different approaches to finding the Nth Fibonacci sequence. All the approaches are explained in detail:

  • Without Using Recursion
  • Using Recursion
  • Using Memoization
  • Using Dynamic Programming
  • Space-optimized Using Loops
  • Using Matrix Multiplication
  • Using Formula
Was this article helpful ?
0 upvotes