Python递归记忆化求第N个斐波那契数报索引越界错误如何解决？

错误原因 #

• 你在fibo函数中初始化的记忆数组a是空列表，Python的列表不允许直接访问超过当前长度的下标。当你传入n=2调用fibonaci时，函数第一时间会尝试访问memo[2]，但空列表没有任何合法下标，直接触发IndexError。
• 就算你给列表开了足够长度，也没有预先给所有位置填充初始值-1，后续判断memo[i]==-1的逻辑也无法正常生效。

修复方案 #

方案1：预初始化固定长度的记忆列表 #

修改fibo函数的记忆数组初始化逻辑，生成一个长度为n+1、所有元素初始值为-1的列表即可：

def fibonaci(i,memo):
    if i == 0 or i == 1:
       return i

    if memo[i]==-1:
       memo[i] = fibonaci(i-1,memo) + fibonaci(i-2,memo)

    return memo[i]

def fibo(n):
    # 初始化长度为n+1的列表，所有值默认填-1
    a = [-1]*(n+1)
    return fibonaci(n,a)

print(fibo(2))

运行后输出正确结果1。

方案2：用字典替代列表做记忆存储（更灵活） #

如果不想提前计算列表长度，也可以用字典来存已经计算过的斐波那契值，不用处理预初始化的问题：

def fibonaci(i,memo):
    if i == 0 or i == 1:
       return i
    if i not in memo:
       memo[i] = fibonaci(i-1,memo) + fibonaci(i-2,memo)
    return memo[i]

def fibo(n):
    a = {}
    return fibonaci(n,a)

print(fibo(2))

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