Fibonacci Series in C++

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

The most efficient and simplest way to calculate Fibonacci numbers is using an iterative approach. This method uses a loop to calculate each Fibonacci number, which is computationally faster than 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(10) 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 = 10, t1 = 0, t2 = 1, nT;  // Hardcoded value of n = 10

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

You can also try this code with Online C++ Compiler

Run Code

Output

0 1 1 2 3 5 8 13 21 34

Fibonacci Series in C++ Using Recursion

Recursion is another way to calculate Fibonacci numbers. It involves a function calling itself, where each function call computes one Fibonacci number until the base case is reached. However, recursion can be inefficient without optimization.

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);
}

You can also try this code with Online C++ Compiler

Run Code

Output

Fibonacci number at position 10 is: 55

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.

Optimized Fibonacci Calculation Using Memoization in C++

Fibonacci series computation can be inefficient due to repeated recursive calls. Using memoization in C++, we can drastically reduce the time complexity by storing previously computed Fibonacci values and reusing them. This optimization avoids redundant calculations and significantly improves the performance of the algorithm.

In the naive recursive approach for calculating Fibonacci numbers, the same subproblems are computed multiple times. This results in exponential time complexity. Memoization, a technique used in dynamic programming, helps us by storing results of expensive function calls and reusing them when needed. By doing so, it reduces the time complexity from O(2^n) to O(n), making it a more efficient solution

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

#define N 1000
int dp[N]; // Array to store previously computed Fibonacci values

// Fibonacci function using memoization
int fibonacci(int n) {
    // If the value is already calculated, return it from the dp array
    if (dp[n] != -1) {
        return dp[n];  // Return the stored result to avoid redundant calculations
    }

    // Base case: return n if n is 0 or 1
    if (n <= 1) {
        dp[n] = n;
    } else {
        // Recursive calls to compute the Fibonacci numbers and store them in dp array
        dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
    }

    return dp[n];
}

int main() {
    int n = 10; // Specify the Fibonacci term you want to compute
    // Initialize the dp array with -1 to signify uncalculated values
    memset(dp, -1, sizeof(dp));

    cout << "The " << n << "th Fibonacci number is: " << fibonacci(n) << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

The 10th Fibonacci number is: 55

Time Complexity: O(n) – With memoization, each Fibonacci value is calculated only once, resulting in a linear time complexity.

Space Complexity: O(n) – The additional space required to store the Fibonacci values in the dp array is proportional to the number of recursive calls.

Try and compile by yourself with the help of online C++ Compiler for better understanding.

Fibonacci Series in C++ Using Dynamic Programming

The Fibonacci series is a sequence where each number is the sum of the two preceding ones. Using Dynamic Programming (DP) in C++, we can efficiently calculate Fibonacci numbers. In this method, we store previously computed Fibonacci numbers to avoid redundant calculations, thus reducing the time complexity. This approach optimizes the performance by calculating each Fibonacci number only once. 

Below is the C++ implementation of Fibonacci using Dynamic Programming.

In this C++ implementation, we use an array dp[] to store the Fibonacci numbers, ensuring that we only calculate each Fibonacci number once. We initialize the first two Fibonacci numbers, dp[0] and dp[1], and then use a loop to calculate the rest of the terms. This approach reduces the time complexity compared to the recursive 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;

    // Loop to calculate Fibonacci numbers up to the nth term
    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]; // Return the nth Fibonacci number
}

int main() {
    int n = 10; // You can change n to get the Fibonacci number at a different position
    
    cout << "The " << n << "th Fibonacci number is: " << fibonacci(n);
}

You can also try this code with Online C++ Compiler

Run Code

Output

The 10th Fibonacci number is: 55

• Time Complexity: O(n) – The loop runs n times, where n is the position of the Fibonacci number to calculate, making this approach linear in time.
   
• Space Complexity: O(n) – The space complexity is O(n) because an array dp[] is used to store Fibonacci numbers up to n. This array consumes O(n) space.

Space-Optimized Fibonacci Calculation Using Loops in C++

The traditional Fibonacci calculation method stores all previous Fibonacci numbers in an array. However, we can optimize the space used in this approach. In this space-optimized version, instead of keeping an entire array, we only need to store the last two Fibonacci numbers. This reduces the space complexity to O(1) while still calculating the Fibonacci number efficiently. 

In this optimized approach, we only store the last two Fibonacci numbers at any given point. This drastically reduces space complexity, as we're no longer storing an entire array. The two variables, prev1 and prev2, hold the last two Fibonacci numbers, and we update them in each iteration of the loop. 

Below is the C++ implementation using loops for space optimization.

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

int fibonacci(int n) {
    // Initialize prev1 and prev2 to store the last two Fibonacci numbers
    int prev1 = 0;
    int prev2 = 1;

    int res;
    // Loop to calculate Fibonacci number using previous two numbers
    for (int i = 2; i <= n; i++) {
        // Add prev1 and prev2 to get the next Fibonacci number
        res = prev1 + prev2;
        // Update prev1 and prev2 for next iteration
        prev1 = prev2;
        prev2 = res;
    }

    return res; // Return the nth Fibonacci number
}

int main() {
    int n = 10; // You can change n to get the nth Fibonacci number
    
    cout << "The " << n << "th Fibonacci number is: " << fibonacci(n);
}

You can also try this code with Online C++ Compiler

Run Code

Output

The 10th Fibonacci number is: 55

• Time Complexity: O(n) – The loop runs n times, where n is the position of the Fibonacci number to calculate. This makes the time complexity linear.
   
• Space Complexity: O(1) – In this space-optimized approach, we only use two variables (prev1 and prev2) to store the last two Fibonacci numbers, resulting in constant space usage.

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);
}

You can also try this code with Online C++ Compiler

Run Code

Time Complexity: O(n)

Space Complexity: O(1)

Calculate Fibonacci Numbers Using the Closed-Form Formula in C++

The Fibonacci sequence is usually calculated iteratively or recursively, but there's also a closed-form expression known as Binet's Formula, which allows us to directly compute the nth Fibonacci number. This method is highly efficient and can be implemented in C++ for quick Fibonacci calculations. 

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

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

Below is the C++ implementation that uses the closed-form formula to find the Fibonacci number at a given position.

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

int fibonacci(int n) {
    // Golden ratio (phi)
    double res = (1 + sqrt(5)) / 2; // φ = (1 + √5) / 2
    // Apply the closed-form formula for Fibonacci numbers
    return round(pow(res, n) / sqrt(5)); // Return the nth Fibonacci number
}

int main() {
    int n = 10; // You can change n to calculate any Fibonacci number
    cout << "The " << n << "th Fibonacci number is: " << fibonacci(n) << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

• Time Complexity: O(log n) – The main operation in this approach is the calculation of the power res^n, which takes logarithmic time (log n) because of the efficient exponentiation algorithm used by pow(). This makes the closed-form method much faster for large n compared to iterative or recursive methods.'
   
• Space Complexity: O(1) – Since we are only using a few variables to store intermediate values (such as res), the space complexity is constant, regardless of the value of n.

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) {
    // Return n if it is 0 or 1 (base cases)
    if (n <= 1)
        return n;
    
    // Initialize the first two Fibonacci numbers
    int prev1 = 0, prev2 = 1, curr;
    
    // Loop to calculate the nth Fibonacci number iteratively
    for (int i = 2; i <= n; i++) {
        curr = prev1 + prev2; // Current Fibonacci number is the sum of the previous two
        prev1 = prev2; // Update prev1 to prev2
        prev2 = curr; // Update prev2 to the current Fibonacci number
    }
    
    // Return the nth Fibonacci number
    return curr;
}

int main() {
    int n = 5; // Change n to find any nth Fibonacci number
    int fibN = fibonacci(n);
    cout << "The " << n << "th Fibonacci number is: " << fibN << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

The 5th Fibonacci number is: 5

• Time Complexity: O(n) – The loop runs n times, each time computing the next Fibonacci number based on the previous two, making it linear in terms of time complexity.
   
• Space Complexity: O(1) – The space complexity is constant since we only use a few variables to store the current and previous Fibonacci numbers, irrespective of the size of n

Dynamic Programming Approach to Find and Print Nth Fibonacci Numbers

The Dynamic Programming (DP) approach is an efficient method for calculating the nth Fibonacci number. This approach avoids redundant calculations by storing previously computed Fibonacci values. By building up the sequence from the base cases, we can compute the nth Fibonacci number in a more optimized manner.

In this example, we’ll look at how to find and print the 5th Fibonacci number using the dynamic programming approach.

#include <iostream>
using namespace std;

int fibonacci(int n) {
    // Create an array dp[] to store Fibonacci values up to n
    int dp[n + 1];
    
    // Base cases
    dp[0] = 0;
    dp[1] = 1;

    // Loop to fill in the dp[] array with Fibonacci numbers
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // Calculate Fibonacci number at index i
    }

    return dp[n]; // Return the nth Fibonacci number
}

int main() {
    int n = 5; // Specify the Fibonacci number to calculate
    int fibN = fibonacci(n); // Get the nth Fibonacci number
    cout << "The " << n << "th Fibonacci number using the dynamic programming approach is: " << fibN << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

The 5th Fibonacci number using the dynamic programming approach is: 5

• Time Complexity: O(n) – The loop runs from 2 to n, and each iteration takes constant time to compute the Fibonacci number at that index. Thus, the time complexity is linear.
   
• Space Complexity: O(n) – We store all the Fibonacci numbers from 0 to n in the array dp[], so the space complexity is O(n).

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.

How do you generate the Fibonacci series?

The Fibonacci series is generated by adding the previous two numbers to obtain the next number. It starts with 0 and 1, producing 0, 1, 1, 2, 3, 5, 8, and so forth. This sequence continues infinitely, exhibiting a pattern of each number being the sum of the two preceding ones.

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:

• Dynamic Binding in C++
• Strong number in C
• Bubble Sort C++
• C++ Interview Questions
• fibonacci series in c
• Turbo C++