The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on. It is named after Leonardo of Pisa, also known as Fibonacci, an Italian mathematician who introduced it to the Western world in his book Liber Abaci, published in 1202.

Problem Statement

Given a positive integer n, find the nth Fibonacci number.

Problem Understanding with Example

Let's understand the problem with an example. Suppose n = 6, we need to find the 6th Fibonacci number. The Fibonacci sequence up to the 6th term is: 0, 1, 1, 2, 3, 5. So, the 6th Fibonacci number is 5.

Solution in C++

Iterative Approach:

#include <iostream>

int fibonacciIterative(int n) {
    int a = 0, b = 1;
    if (n == 0)
        return a;
    for (int i = 2; i <= n; ++i) {
        int temp = b;
        b = a + b;
        a = temp;
    }
    return b;
}

int main() {
    int n = 10; // Change the value of n as needed
    std::cout << "Fibonacci sequence up to " << n << " terms using iteration: ";
    for (int i = 0; i < n; ++i) {
        std::cout << fibonacciIterative(i) << " ";
    }
    return 0;
}

Recursive Approach:

#include <iostream>

int fibonacciRecursive(int n) {
    if (n <= 1)
        return n;
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

int main() {
    int n = 10; // Change the value of n as needed
    std::cout << "Fibonacci sequence up to " << n << " terms using recursion: ";
    for (int i = 0; i < n; ++i) {
        std::cout << fibonacciRecursive(i) << " ";
    }
    return 0;
}

Dynamic Approach (Memoization) Top-Down:

#include <iostream>
#include <vector>

std::vector<int> memo;

int fibonacciMemoization(int n) {
    if (n <= 1)
        return n;
    if (memo[n] != -1)
        return memo[n];
    memo[n] = fibonacciMemoization(n - 1) + fibonacciMemoization(n - 2);
    return memo[n];
}

int main() {
    int n = 10; // Change the value of n as needed
    memo.resize(n + 1, -1);
    std::cout << "Fibonacci sequence up to " << n << " terms using memoization: ";
    for (int i = 0; i < n; ++i) {
        std::cout << fibonacciMemoization(i) << " ";
    }
    return 0;
}

Dynamic Approach (Tabulation) Bottom-Up Approach:

#include <iostream>
#include <vector>

int fibonacciTabulation(int n) {
    if (n <= 1)
        return n;
    std::vector<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 = 10; // Change the value of n as needed
    std::cout << "Fibonacci sequence up to " << n << " terms using tabulation: ";
    for (int i = 0; i < n; ++i) {
        std::cout << fibonacciTabulation(i) << " ";
    }
    return 0;
}

Complexity Analysis

Iterative Approach:

Time Complexity: The time complexity of the iterative approach is O(n). This is because it iterates through the loop exactly n times, each time performing constant-time operations to update the values of a and b.

Space Complexity: The space complexity of the iterative Fibonacci algorithm is O(1). This 

Recursive Approach:

Time Complexity: The time complexity of this recursive approach is exponential, O(2 ^ n). This is because each call branches into two more calls, leading to a binary tree of recursive calls. As a result, the number of function calls grow exponentially with the input size.

Space Complexity: The space complexity of the recursive Fibonacci algorithm is also exponential, specifically O(n). This is because it requires space on the call stack for each recursive call until it reaches the base case.

Dynamic Programming:

Time Complexity: With memoization, the time complexity reduces drastically to O(n). This is because each value is computed only once and stored in the memoization array. Subsequent calls for the same value directly retrieve the computed result from memory, avoiding redundant computations.

Space Complexity: The space complexity of the memoized Fibonacci algorithm is O(n). This is because it requires space for the memoization table of size n to store the computed values.