cppadvanced10 minutes

Build a Memoized Recursive Function to Calculate Large Fibonacci Numbers

Implement an efficient recursive function in C++ that computes the nth Fibonacci number leveraging memoization to optimize overlapping subproblems, capable of handling large input values.

Challenge prompt

Create a function `long long fib(int n)` that returns the nth Fibonacci number (0-indexed: fib(0) = 0, fib(1) = 1). The function must use recursion with memoization to handle inputs up to at least n = 90 efficiently. Avoid recomputation by caching intermediate results.

Guidance

• Use a static or external container like `std::unordered_map` or `std::vector` to store previously computed Fibonacci values.
• Implement the base cases for n=0 and n=1 explicitly in the recursive function.
• Make sure the function runs efficiently for large n by avoiding redundant recursive calls.

Hints

• Consider passing the memoization container as a static variable inside the function to preserve data across calls.
• Use `long long` as the return type to safely store Fibonacci numbers up to fib(90).
• Test edge cases like fib(0), fib(1), and fib(90) to ensure correctness and performance.

Starter code

long long fib(int n) {
    // Your code here
}

Expected output

fib(10) = 55 fib(50) = 12586269025 fib(90) = 2880067194370816120

Core concepts

recursionmemoizationdynamic programmingoptimization

Challenge a Friend

Send this duel to someone else and see if they can solve it.