Implement a Custom Memoized Recursive Function for Large Fibonacci Numbers
Write an optimized C++ function to compute Fibonacci numbers using memoization. The function must efficiently handle very large inputs by caching intermediate results to avoid exponential time complexity, showcasing mastery of recursion, dynamic programming, and function optimization.
Challenge prompt
Create a C++ function named fibonacciMemo that takes a single unsigned integer n and returns the nth Fibonacci number as an unsigned long long. The function must be implemented using recursion and memoization (caching previously computed values) to handle large n values (e.g., n up to 90) efficiently without excessive computation or stack overflow. Avoid global variables for caching; encapsulate memoization logic within the function or helper structures.
Guidance
- • Use a data structure like std::unordered_map or std::vector to store already computed Fibonacci numbers to avoid redundant calculations.
- • Define a helper function or use lambda recursion with a memo container passed by reference to keep track of the intermediate results.
- • Ensure the function handles base cases (n = 0 and n = 1) correctly to avoid infinite recursion.
Hints
- • Remember that naive recursive Fibonacci computation has exponential time complexity; memoization reduces this to linear.
- • Using std::unordered_map for memoization works but might be slower than std::vector when n is known and limited.
- • Be cautious with unsigned long long overflow for very large Fibonacci numbers; this challenge assumes n within the 64-bit result range.
Starter code
unsigned long long fibonacciMemo(unsigned int n) {
// Implement this function
}Expected output
fibonacciMemo(10) == 55 fibonacciMemo(50) == 12586269025 fibonacciMemo(90) == 2880067194370816120
Core concepts
Challenge a Friend
Send this duel to someone else and see if they can solve it.