Algocademy Logo

Recursive Fibonacci in C++ with Time Complexity Analysis


The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Write a recursive function that given n, returns F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:
  • 0 <= n <= 30
Note:

Don't worry about the time and space complexities of your algorithm.


Hints:

Inside the function, we should first check the base case: if n is less than 2, then we should return n.

If n >= 2, since F(n) = F(n - 1) + F(n - 2), we should return fibonacci(n - 1) + fibonacci(n - 2).

Understanding the Problem

The core challenge of this problem is to compute the nth Fibonacci number using a recursive approach. The Fibonacci sequence is a classic example in computer science and mathematics, often used to teach recursion and dynamic programming.

Common applications of the Fibonacci sequence include algorithm analysis, financial models, and biological settings like population growth models.

Potential pitfalls include misunderstanding the base cases and not recognizing the exponential time complexity of the naive recursive approach.

Approach

To solve this problem, we can start with a naive recursive solution and then discuss its limitations. We will then explore optimized solutions.

Naive Recursive Solution

The naive approach directly translates the mathematical definition into code. However, this approach has exponential time complexity, O(2^n), due to repeated calculations of the same subproblems.

Optimized Solutions

1. **Memoization**: Store the results of subproblems to avoid redundant calculations. This reduces the time complexity to O(n).

2. **Iterative Approach**: Use a loop to compute the Fibonacci numbers iteratively, which also has O(n) time complexity but with constant space complexity, O(1).

Algorithm

Naive Recursive Algorithm

1. If n is 0, return 0.
2. If n is 1, return 1.
3. Otherwise, return fibonacci(n-1) + fibonacci(n-2).

Memoization Algorithm

1. Create a memoization array initialized to -1.
2. If n is 0 or 1, return n.
3. If the value is already computed, return it.
4. Otherwise, compute the value, store it in the array, and return it.

Iterative Algorithm

1. Initialize two variables to store the previous two Fibonacci numbers.
2. Use a loop to compute the Fibonacci numbers up to n.
3. Return the nth Fibonacci number.

Code Implementation

Naive Recursive Solution


#include <iostream>

// Naive recursive function to find nth Fibonacci number
int fibonacci(int n) {
    // Base cases
    if (n == 0) return 0;
    if (n == 1) return 1;
    // Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n = 4;
    std::cout << "F(" << n << ") = " << fibonacci(n) << std::endl;
    return 0;
}

Memoization Solution


#include <iostream>
#include <vector>

// Memoization function to find nth Fibonacci number
int fibonacci(int n, std::vector<int> &memo) {
    // Base cases
    if (n == 0) return 0;
    if (n == 1) return 1;
    // Check if value is already computed
    if (memo[n] != -1) return memo[n];
    // Compute and store the value
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return memo[n];
}

int main() {
    int n = 4;
    std::vector<int> memo(n + 1, -1);
    std::cout << "F(" << n << ") = " << fibonacci(n, memo) << std::endl;
    return 0;
}

Iterative Solution


#include <iostream>

// Iterative function to find nth Fibonacci number
int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n = 4;
    std::cout << "F(" << n << ") = " << fibonacci(n) << std::endl;
    return 0;
}

Complexity Analysis

**Naive Recursive Solution**: Time complexity is O(2^n) and space complexity is O(n) due to the call stack.

**Memoization Solution**: Time complexity is O(n) and space complexity is O(n) due to the memoization array.

**Iterative Solution**: Time complexity is O(n) and space complexity is O(1).

Edge Cases

1. **n = 0**: The function should return 0.

2. **n = 1**: The function should return 1.

3. **n = 30**: The function should handle the upper constraint efficiently.

Testing

To test the solution comprehensively, consider the following test cases:

Use a testing framework like Google Test for automated testing.

Thinking and Problem-Solving Tips

1. **Understand the problem**: Break down the problem into smaller parts and understand the base cases.

2. **Start with a naive solution**: Implement the simplest solution first, then optimize.

3. **Use memoization**: Store results of subproblems to avoid redundant calculations.

4. **Practice**: Solve similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed the recursive Fibonacci problem, explored naive and optimized solutions, and analyzed their complexities. Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science.

Practice and explore further to master these concepts.

Additional Resources