Python记忆化斐波那契递归函数报错1≠0问题排查

嘿，我来帮你拆解下这个斐波那契记忆化函数的问题根源，以及怎么修复：

三个核心错误点 #

1. 记忆化字典完全没起作用：你把memo = {}放在了fib_memoize函数内部，每次调用这个函数（包括递归调用）都会新建一个空字典！之前计算过的斐波那契值根本存不住，等于白写了记忆化逻辑。
2. 递归调用错了函数：你在计算f的时候调用的是fib_recursive，而不是fib_memoize——这相当于绕开了记忆化逻辑，还是在用最原始的O(2^n)时间复杂度的递归，完全没利用到缓存。
3. 基准条件不匹配：你的fib_memoize里写的是n<=2返回1，但fib_recursive的基准条件是n<=1返回对应值（比如根据断言错误1 !=0，推测fib_recursive(1)返回0，fib_recursive(2)返回1），这就导致当n=1时，两个函数返回值不一致，触发断言失败。

修复后的可行代码 #

这里给你两种常用的记忆化写法，都是O(n)时间复杂度：

方案1：嵌套辅助函数（推荐，作用域更清晰） #

def fib_memoize(n):
    # memo只在第一次调用fib_memoize时初始化一次
    memo = {}
    
    def helper(k):
        if k in memo:
            return memo[k]
        # 和fib_recursive的基准条件严格对齐
        if k <= 1:
            res = k  # 对应fib_recursive(0)=0, fib_recursive(1)=1
        else:
            # 递归调用带记忆化的helper，而非原始递归
            res = helper(k-1) + helper(k-2)
        memo[k] = res
        return res
    
    return helper(n)

方案2：用默认参数传递缓存 #

def fib_memoize(n, memo=None):
    # 只有第一次调用时初始化memo，后续递归复用同一个字典
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    # 对齐fib_recursive的基准条件
    if n <= 1:
        f = n
    else:
        # 递归调用fib_memoize，传递同一个memo字典
        f = fib_memoize(n-1, memo) + fib_memoize(n-2, memo)
    memo[n] = f
    return f

验证说明 #

修复后，每个斐波那契数只会被计算一次，之后直接从memo中读取，时间复杂度降到O(n)。同时基准条件和fib_recursive完全一致，不会再出现返回值不匹配的断言错误。

内容的提问来源于stack exchange，提问作者user7732694