pythonadvanced15 minutes

Build a Memoized Recursive Fibonacci Function with Performance Tracking

Create a Python function to compute Fibonacci numbers using memoization to optimize recursive calls. Additionally, implement performance tracking to count how many times the function is called and how many cache hits occur.

Challenge prompt

Write a Python function named fibonacci(n) that returns the nth Fibonacci number. Use memoization to optimize the recursive calls. Additionally, implement internal tracking mechanisms inside your function or via helper structures to count the total number of function calls made and the number of times a cached value was returned instead of performing a full recursion. Your function should expose two additional attributes: call_count and cache_hits, which track these metrics respectively. For example, calling fibonacci(10) should return 55, and the attributes fibonacci.call_count and fibonacci.cache_hits should reflect the optimization achieved. Requirements: - Use plain recursion combined with memoization (caching previously computed results). - Track the total number of fibonacci function calls, including cache lookups. - Track the number of cache hits where a cached result is reused. - Expose call_count and cache_hits as attributes accessible as fibonacci.call_count and fibonacci.cache_hits. Implement efficient and clean code to achieve this.

Guidance

• Use a dictionary to cache computed Fibonacci values and check it before performing recursive calls.
• Increment call_count each time the fibonacci function is called.
• Increment cache_hits each time you return a cached value without recursion.

Hints

• Consider defining the call_count and cache_hits attributes on the function object itself.
• Make sure to handle the base cases of Fibonacci (n=0 returns 0, n=1 returns 1) properly.
• Try wrapping your recursive function inside another function or use Python function attributes for tracking.

Starter code

def fibonacci(n):
    # Initialize cache and counters on the first call if needed
    if not hasattr(fibonacci, 'cache'):
        fibonacci.cache = {0: 0, 1: 1}
        fibonacci.call_count = 0
        fibonacci.cache_hits = 0
    fibonacci.call_count += 1
    if n in fibonacci.cache:
        fibonacci.cache_hits += 1
        return fibonacci.cache[n]
    result = fibonacci(n-1) + fibonacci(n-2)
    fibonacci.cache[n] = result
    return result

Expected output

fibonacci(10) == 55 fibonacci.call_count > 0 fibonacci.cache_hits > 0

Core concepts

recursionmemoizationfunction attributesperformance tracking

Challenge a Friend

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