Fibonacci series in C++

Introduction

Leonardo Fibonacci was an Italian mathematician who introduced the Fibonacci Series to the Western world in his book "Liber Abaci". The series starts with 0 and 1, and the rest of the numbers are generated by adding the last two numbers in the sequence.

In this article, you will learn how to generate the Fibonacci series in C++.

What is a Fibonacci Series?

The Fibonacci series is a sequence of numbers in which each number is the sum of the two numbers before it.

For example, { 0, 1, 1, 2, 3, 5, 8, 13, 21 } and so on.

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

Different Approaches for Finding the Fibonacci Series in C++

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

We will now discuss these different approaches to finding the Fibonacci series in C++ 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 itself
    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
Try and compile by yourself with the help of online C++ Compiler for better understanding.

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.

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

After multiplication, we will put the result in another 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

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, 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 = 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]ⁿ} / √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)

Iterative Approach to Find and Print Nth Fibonacci Numbers

We can find the nth Fibonacci number using a simple for loop. We can initiate the first two variables as 0 and 1, and we will keep on updating them till we don't find the nth Fibonacci number. Let us look at the code below to find and print the 5th Fibonacci number.

#include <iostream>
using namespace std;
int fibonacci(int n) {
   if (n <= 1)
       return n;
   int prev1 = 0, prev2 = 1, curr;
   for (int i = 2; i <= n; i++) {
       curr = prev1 + prev2;
       prev1 = prev2;
       prev2 = curr;
   }
   return curr;
}
int main() {
   int n=5;
   int fibN = fibonacci(n);
   cout << "The " << n << "th Fibonacci number is: " << fibN << endl;
   return 0;
}

Output

Time Complexity: O(n)

Space Complexity: O(1)

Dynamic Programming Approach to Find and Print Nth Fibonacci Numbers

We can also use the Dynamic programming approach to find and print the Nth Fibonacci number. In this method, we store previous Fibonacci values to find the current Fibonacci number. Let us take an example of finding and printing the 5th Fibonacci number using dynamic programming to make it more clear for you.

#include <iostream>
using namespace std;
int fibonacci(int n) {
   int dp[n + 1];
   dp[0] = 0;
   dp[1] = 1;
   for (int i = 2; i <= n; i++) {
       dp[i] = dp[i - 1] + dp[i - 2];
   }
   return dp[n];
}
int main() {
   int n=5;
   int fibN = fibonacci(n);
   cout << "The " << n << "th Fibonacci number using dynamic programming approach is: " << fibN << endl;
   return 0;
}

Output

Time Complexity: O(n)

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

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 is the 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.

What is the base logic for Fibonacci series?

The base logic for finding the Fibonacci series is the same as its definition; the Nth value of the Fibonacci series is equal to the sum of (N-1)th and (N-2)th values. You can implement this base logic with different techniques such as loops, recursion, matrix multiplication, etc.

What are the 9 term of Fibonacci series?

The first 9 terms of the Fibonacci series are 0, 1, 1, 2, 3, 5, 8, 13, and 21. You can find these terms using the different methods we have discussed in this article, such as matrix multiplication, loops, formula, and recursion.

What is Fibonacci series using recursion?

You can find the Nth term of the Fibonacci series using the recurrence relation, fib(n) = fib(n-1) + fib(n-2). The recursive method can be further optimized using memoization which helps you avoid recalculating the same result.

Conclusion

This article discusses the Fibonacci Series in C++ and the different approaches to finding the Nth Fibonacci sequence. The following approaches are explained in detail: Without Using Recursion, Using Recursion, Using Memoization, Using Dynamic Programming, Space-optimized Using Loops, Using Matrix Multiplication, Using Formula.

Recommended Readings: