"How can I optimize a recursive algorithm for calculating Fibonacci numbers in C++?"

Question

I'm working on a project that involves calculating Fibonacci numbers in C++ using a recursive algorithm. My current implementation follows the traditional recursive approach, but it exhibits performance issues for larger Fibonacci numbers. Here's what I've done so far:

#include <iostream>

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

int main() {
    int n = 10; // Example: Calculate Fibonacci(10)
    std::cout << "Fibonacci(" << n << ") = " << fibonacci(n) << std::endl;
    return 0;
}

I've noticed that for Fibonacci numbers beyond a certain value, the algorithm becomes slow and consumes a lot of memory.I've been exploring ways to optimize this algorithm, but I'm not sure where to start. Are there any techniques or strategies I can use to make it faster and more memory-efficient? I'd appreciate any guidance or code examples that can help me improve the performance of my Fibonacci calculator.

Answer 1

Use memoization so you don't have to recalculate the same Fibonacci numbers many times. I.e., maintain a map of n->fib(n), and check it before calculating a Fibonacci numbers. If n isn't a key, go ahead and calculate, otherwise return the associated value.