pythonadvanced15 minutes

Fix the Memory Leak in a Recursive Fibonacci with Memoization

Identify and fix the bug in a recursive Fibonacci function that uses memoization but causes unintended memory growth or incorrect results due to faulty cache handling.

Challenge prompt

You're given a Python function that computes the nth Fibonacci number using recursion and memoization with a dictionary cache. However, the current implementation has a bug that causes either a memory leak or incorrect caching leading to wrong outputs for larger inputs. Fix the code so that the function correctly computes the Fibonacci numbers efficiently without causing excess memory use or incorrect caching.

Guidance

• Analyze how the cache dictionary is initialized and used in the recursive calls.
• Ensure the cache does not reset during recursion causing unnecessary recomputation or memory misuse.
• Validate that the base cases and recursive conditions are handled correctly so the function terminates as expected.

Hints

• Check if the cache dictionary is being re-created inside the recursive function call.
• Consider passing the cache dictionary as a default argument or using a helper function to maintain state.
• Verify the function returns the memoized value correctly and stores it after computation.

Starter code

def fibonacci(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache = {}  # Bug: reinitializing cache inside recursion
    cache[n] = fibonacci(n-1, cache) + fibonacci(n-2, cache)
    return cache[n]

Expected output

fibonacci(10) should return 55 fibonacci(20) should return 6765

Core concepts

recursionmemoizationmutable default argumentsdebugging

Challenge a Friend

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