Implement a High-Performance Memoized Fibonacci Function Using C++17 Features
Create an optimized recursive Fibonacci function that uses memoization with modern C++17 features such as std::unordered_map and constexpr optimizations to achieve efficient calculations for large Fibonacci indices.
Challenge prompt
Write a C++ function named fibonacci that takes a single unsigned integer n and returns the nth Fibonacci number. Your solution must use memoization to avoid repeated calculations and be optimized for performance. Use C++17 features where appropriate, such as structured bindings or inline variables, to enhance readability and efficiency. The Fibonacci sequence is defined as: Fib(0) = 0, Fib(1) = 1, and Fib(n) = Fib(n-1) + Fib(n-2) for n >= 2.
Guidance
- • Use a static or external cache (e.g., unordered_map or vector) to store previously computed Fibonacci values.
- • Consider thread-safety if using static variables, but for this challenge focus on single-threaded performance.
- • Leverage C++17 features like structured bindings or inline variables to simplify code where suitable.
Hints
- • Memoization can be implemented using recursion combined with a map that stores intermediate results to prevent redundant calls.
- • Since Fib(0) and Fib(1) are base cases, initialize them in your cache before starting recursion.
- • Try to avoid recomputing the same Fibonacci number multiple times by checking the cache before making recursive calls.
Starter code
unsigned long long fibonacci(unsigned int n) {
// TODO: Implement memoized Fibonacci
}Expected output
fibonacci(10) == 55 fibonacci(50) == 12586269025
Core concepts
Challenge a Friend
Send this duel to someone else and see if they can solve it.