pythonadvanced15 minutes

Fix Bug in Advanced Memoized Recursive Fibonacci Implementation

Identify and fix the bug in a recursive Fibonacci function optimized with memoization to achieve efficient performance for large input values.

Challenge prompt

The following code is intended to compute the nth Fibonacci number efficiently using memoization (caching previously computed values). However, it currently produces incorrect results or runs inefficiently for larger inputs. Identify and fix the bug(s) so that it computes the correct Fibonacci number with optimal performance.

Guidance

• Check the memoization dictionary usage and key handling to ensure cached values are stored and retrieved correctly.
• Validate the base cases are correctly defined to prevent infinite recursion.
• Test behavior on both small and large inputs to confirm correctness and efficiency.

Hints

• Make sure all code paths update and return the cached results correctly.
• Look closely at the base case return values and whether they correlate correctly with the Fibonacci sequence definition.

Starter code

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo-1)  # Bug here
    return memo[n]

Expected output

fib(10) should return 55 fib(50) should return 12586269025

Core concepts

memoizationrecursiondebugging

Challenge a Friend

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