C++ Program to Display Fibonacci Series

Introduction

The Fibonacci series is a sequence where each number is the sum of the two preceding ones, usually starting with 0 and 1. It's a classic example used in programming to teach recursion, loops, and illustrates the effectiveness of dynamic programming. In C++, implementing the Fibonacci series is both straightforward and a great way to understand basic constructs such as loops and recursion.

In this article, you will learn how to implement the Fibonacci series in C++ using different methods. Gain insights into using iterative approaches, recursive functions, and even C++'s more advanced features to generate the Fibonacci sequence effectively.

Iterative Approach to Fibonacci Series

Using a For Loop

1. Begin with initializing the first two numbers of the Fibonacci series (0 and 1).

2. Use a for loop to iterate and generate the next numbers of the series.

   cpp Copy

   #include <iostream>
   using namespace std;
   
   void printFibonacci(int n) {
       int t1 = 0, t2 = 1, nextTerm = 0;
   
       // Displaying the first two terms which are always 0 and 1
       cout << t1 << ", " << t2 << ", ";
   
       for (int i = 2; i < n; ++i) {
           nextTerm = t1 + t2;
           t1 = t2;
           t2 = nextTerm;
           cout << nextTerm << ", ";
       }
   }
   
   int main() {
       int n = 10;  // number of terms to be printed in the Fibonacci series
       printFibonacci(n);
       return 0;
   }
   

   This function begins by printing the first two terms (0 and 1). The loop then continues from the second index, calculating the next term by summing up the last two terms. With each iteration, the values of t1 and t2 are updated.

Recursive Approach to Fibonacci Series

Using a Recursive Function

1. Define a recursive function that calls itself to compute each Fibonacci number.

2. Handle the base cases within the function to avoid infinite recursion.

   cpp Copy

   #include <iostream>
   using namespace std;
   
   int fibonacci(int n) {
       if (n <= 1)
           return n;
       return fibonacci(n - 1) + fibonacci(n - 2);
   }
   
   int main() {
       int n = 10;
       for (int i = 0; i < n; ++i) {
           cout << fibonacci(i) << ", ";
       }
       return 0;
   }
   

   The fibonacci function in this snippet recursively calculates Fibonacci numbers. The recursion breaks when n is 0 or 1, which are the base cases. Each function call stacks until it reaches the base case, then unwinds, summing up the results to produce the final output.

Using Dynamic Programming with Memoization

Implementing Memoization to Optimize the Recursive Solution

1. Implement memoization by storing previously computed values of the Fibonacci sequence.

2. Modify the recursive function to check if the value has already been computed.

   cpp Copy

   #include <iostream>
   #include <vector>
   using namespace std;
   
   vector<int> fibCache(100, -1);  // a large array to store computed Fibonacci numbers
   
   int fibonacci(int n) {
       if (n <= 1)
           return n;
       if (fibCache[n] != -1)
           return fibCache[n];
       fibCache[n] = fibonacci(n - 1) + fibonacci(n - 2);
       return fibCache[n];
   }
   
   int main() {
       int n = 10;
       for (int i = 0; i < n; ++i) {
           cout << fibonacci(i) << ", ";
       }
       return 0;
   }
   

   This example uses a vector named fibCache to store the results of each Fibonacci number as they are calculated. This prevents the repetitive work that a plain recursive approach entails, significantly enhancing performance. The efficient management of previous results cuts down computation time from exponential to linear.

Conclusion

The Fibonacci series not only serves as a fundamental algorithmic problem but also provides insights into various programming approaches in C++. From iterative and simple recursive methods to an optimized solution using dynamic programming, each method offers different advantages. By mastering these techniques, you ensure that solutions are not only correct but also efficient in terms of execution time and resource usage, crucial for solving more complex problems in computer science. Follow these examples to explore the diverse capabilities of C++ in algorithm implementation.