手动缓存实现Python斐波那契函数：两版本原理及正确性疑问

import time
def fib_cache(n, cache={}):
    if n in cache:
        return cache[n]
    if n == 0 or n == 1:
        return n
    result = fib_cache(n - 1) + fib_cache(n - 2)
    cache[n] = result
    return result
def fib_cache2(n, cache={}):
    if n in cache:
        return cache[n]
    if n == 0 or n == 1:
        return n
    result = fib_cache2(n - 1, cache) + fib_cache2(n - 2, cache)
    cache[n] = result
    return result
start = time.perf_counter()
fib_cache(30)
end = time.perf_counter()
print("Version 1. Seconds taken: {:.5f}".format(end - start))
start = time.perf_counter()
fib_cache2(30)
end = time.perf_counter()
print("Version 2. Seconds taken: {:.5f}".format(end - start))

这是个非常典型的Python默认参数特性问题，咱们一步步说清楚：

为什么第一个版本fib_cache能正常工作？ #

核心原因是Python的默认参数是在函数定义时初始化的，而不是每次调用时：

• 当你写def fib_cache(n, cache={}):时，这个空字典{}就已经被创建了，并且会绑定到函数的默认参数上。
• 之后每次调用fib_cache（包括递归调用），只要没显式传入cache参数，都会复用同一个字典对象。
• 递归调用fib_cache(n-1)和fib_cache(n-2)时，因为没传cache，所以它们用的和外层函数是同一个缓存字典——计算过的斐波那契值会被存在这个字典里，彻底避免了重复计算，所以比非记忆化版本快很多。

不过要注意：这个特性也有“小坑”——如果你多次调用fib_cache（比如先算fib_cache(30)再算fib_cache(20)），缓存会保留之前的结果，这可能是你想要的，但也可能在某些场景下导致意料之外的缓存污染。

第二个版本fib_cache2是否更符合规范？ #

答案是是的，它更清晰、更符合代码可读性规范：

• 虽然功能上它和第一个版本等价（因为传入的cache就是同一个默认字典对象），但它显式地把缓存传递给递归调用，让阅读代码的人一眼就能明白：递归过程是共享同一个缓存的，不需要依赖Python默认参数的隐式特性。
• 为什么性能提升不显著？因为第一个版本已经在复用同一个缓存了，第二个版本只是多了一步参数传递，但Python的参数传递是引用传递，这个额外开销极小，所以速度差异微乎其微。

额外建议：更安全的记忆化写法 #

如果想避免第一个版本的缓存污染问题（比如多次调用时不想共享缓存），可以改成用None作为默认参数，在函数内部初始化缓存：

def fib_cache_safe(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n == 0 or n == 1:
        return n
    result = fib_cache_safe(n - 1, cache) + fib_cache_safe(n - 2, cache)
    cache[n] = result
    return result

这样每次调用fib_cache_safe如果不传cache，都会创建一个新的空字典，避免了跨调用的缓存累积。

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