用Python字典实现记忆化求斐波那契数：字典存储与命名空间疑问

代码与运行结果 #

实现代码 #

def fib(n, d = {}):
    if n in d:
        return d[n]
    elif n < 3:
        return 1
    else:
        d[n] = fib(n - 1, d) + fib(n - 2, d)
        print(f"n: {n}")
        print(f"d: {d}")
        return d[n]

print("fib(6):", fib(6))
print("fib(7):", fib(7))
print("fib(8):", fib(8))

运行输出 #

n: 3
d: {3: 2}
n: 4
d: {3: 2, 4: 3}
n: 5
d: {3: 2, 4: 3, 5: 5}
n: 6
d: {3: 2, 4: 3, 5: 5, 6: 8}
fib(6): 8
n: 7
d: {3: 2, 4: 3, 5: 5, 6: 8, 7: 13}
fib(7): 13
n: 8
d: {3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21}
fib(8): 21

疑问解答 #

• 字典d存储在何处？
  Python函数的默认参数是在函数定义阶段就创建绑定的，这个d = {}字典会存在fib函数的__defaults__属性里，属于函数对象的一部分。只要函数对象没被销毁，这个字典就会一直保留，你可以直接在控制台打印fib.__defaults__查看它的内容。

• 为什么调用fib(7)和fib(8)能快速返回结果？
  第一次调用fib(6)时，已经把3到6的斐波那契计算结果缓存到了d里。后续调用fib(7)时，只需要直接取d中已有的fib(6)和fib(5)的值相加，不用再递归重复计算前面的所有项；fib(8)同理，直接取d里的7和6的值求和即可。这就是记忆化的核心作用——用缓存避免重复计算，大幅提升效率。

• d的命名空间是什么？它是否被当作全局变量处理？
  d不属于全局命名空间，它是绑定在fib函数自身的默认参数对象，属于函数的内部关联属性。虽然它的生命周期和全局变量类似（只要函数存在就不会消失），但它不是全局变量——全局变量是定义在模块最外层的，而这个d是依附于函数对象存在的。另外，只要调用函数时不手动传入d参数，所有调用都会共享这个默认字典，这也是后续调用能复用缓存结果的原因。

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