Various Programs For Fibonacci Numbers In C++

Various Programs For Fibonacci Numbers In C++

Introduction

The Fibonacci sequence is a sequence in which each number is the sum of the preceding two numbers. By default, 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

This article will discuss various approaches and the respective program to find the nth Fibonacci number. We will be given a number n, and the task is to find the nth number in the Fibonacci series.

Before moving on to the solution, you can try to solve this problem on CodeStudio.

Following are the different programs for Fibonacci numbers.

Using Recursion

We can simply find the nth Fibonacci number using the simple mathematical recurrence relation given below.

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 it recursively calls itself and returns fibonacci(n-1) + fibonacci(n-2);

Below is the implementation of the recursive program for Fibonacci numbers.

#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.

The above diagram shows a function call for calculating the fourth Fibonacci number. On taking a closer look at the diagram you will notice that we are making repeated calls for the same values.

Calls for the same values are highlighted in the same color in the diagram. We can avoid these repeated calls and improve the time complexity of our code. 

Using Memoization

In the recursive programs for Fibonacci numbers discussed above, we were making repetitive calls to function for the same value, increasing the time complexity of our code. But we can improve this, if we can store values for these calls, we can reduce the complexity of the program to a huge extent.

We will make the recursive call, but this time we will be storing the value for each recursive call in an array, thus making sure that we are doing the whole recursive calculation for a value only once.

Below is the Memoization implementation of the programs 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

The basic idea is, to sum up, the previous two numbers to get the following term and keep on repeating this process until we get the nth term. We will make an array to store values of elements and use a loop to sum previous elements to get the Fibonacci element.

Below are the programs 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 for 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

This method relies on the mathematical fact that if we 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. 

The matrix representation for the above statement can be given as

The most crucial part of implementing this approach is matrix multiplication. We will be multiplying the 2X2 matrix. A 2X2 matrix is multiplied in the following manner.

Suppose we have the following two matrices, and after multiplying these two, we have to put the result in another matrix c.

After multiplication, we will get the following values for matrix C.

Suppose we want to find the fourth Fibonacci number then we need to calculate the following:

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

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

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

We will be using this result to multiply the matrix in our code. You can read about matrix multiplication in detail here.

#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

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

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

You can study more about this formula in detail here.

#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 print or generate the Fibonacci series, which is a series in which each number is the sum of the preceding two numbers. By default, the first two numbers of a Fibonacci series are 0 and 1.

How do you use Fibonacci programming?

Fibonacci programming is used to encode integers in binary code.

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, 6765 are the first Fibonacci numbers.

How do you print a Fibonacci sequence?

A Fibonacci sequence is the integer sequence of 0, 1, 1, 2, 3, 5, 8… The first two terms are 0 and 1. All other terms are obtained by adding the preceding two terms.to print the Fibonacci series.

Is 0 a Fibonacci number?

Yes,0 is a Fibonacci number.

Key Takeaways

This article discusses the program for Fibonacci numbers with methods like recursion, memoization, dynamic programming, space-optimized DP, using matrix multiplication, and using formulas to find the Fibonacci series.

You should try to implement this problem on CodeStudio without any login.

Also, try Fibonacci Series In Python.

CodeStudio is a platform developed by aspiring enthusiasts and working professionals who have experience in companies like Google, Amazon, Microsoft. At CodeStudio, you get interview problems, interview experiences, and practice problems that can help you to land your dream job. 

By Pranchal Agrahari

Exit mobile version