Fix the Infinite Recursion Bug in a Python Memoization Function
Identify and fix a subtle bug causing infinite recursion in a Python function designed to compute Fibonacci numbers with memoization. The code uses a dictionary cache but incorrectly implements memoization logic, leading to recursion errors. Your task is to debug the function to correctly utilize memoization and efficiently compute Fibonacci values.
Challenge prompt
The provided Python function is intended to compute the nth Fibonacci number using memoization to optimize repeated calculations. However, it produces a RuntimeError due to infinite recursion. Identify and fix the bug causing this infinite recursion so that the function returns the correct Fibonacci number efficiently. Preserve the memoization approach in your fix.
Guidance
- • Review how the function uses the cache dictionary to store computed Fibonacci values.
- • Check the base cases to ensure proper termination of recursion.
- • Ensure that the recursive results are stored in the cache before returning.
Hints
- • The cache assignment might be placed incorrectly or missing before the recursive return.
- • If you omit storing the computed result in the cache, recursive calls will never resolve.
- • Confirm that the function checks the cache before computing new Fibonacci values.
Starter code
def fib(n, cache={}):
if n == 0:
return 0
if n == 1:
return 1
if n not in cache:
return fib(n - 1, cache) + fib(n - 2, cache)
return cache[n]Expected output
fib(10) should return 55
Core concepts
Challenge a Friend
Send this duel to someone else and see if they can solve it.