为什么下面的递归函数不使用缓存中的值来返回值？

Question

我创建了一个 python 函数来计算第 n 个斐波那契项。为了提高效率，我使用了cache_mem 字典来存储变量。当我调试该函数时，它会遍历所有函数调用，而不是使用缓存的存储变量。为什么会出现这种情况？

cache_mem = {}

def fib(n):
    if n <= 1:
        return n
    else:
        cache_mem[n-1] = cache_mem.get(n-1, fib(n-1))
        cache_mem[n-2] = cache_mem.get(n-2, fib(n-2))

        return cache_mem[n-1] + cache_mem[n-2]

我希望cache_mem字典能够存储结果的值，并使用它们而不是调用函数。根据我的理解，这条线

cache_mem[n-1] = cache_mem.get(n-1, fib(n-1))

将检查字典中 n-1 的值。如果存在，它将返回值，否则它将计算值。

Answer 1

函数的参数都在调用函数之前进行评估。所以当你写的时候

cache_mem.get(n-1, fib(n-1)) 它首先必须执行

fib(n-1)

，然后再调用

cache_mem.get()

。所以缓存永远不会阻止调用。

用明确的条件替换它：

if n-1 not in cache_mem:
    cache_mem[n-1] = fib(n-1)

顺便说一句，Python 有一个

functools.cache

装饰器可以为函数添加自动缓存。

Answer 2

在代码中，您不会根据元素是否在缓存中来中断递归调用。需要进行类似“如果我们已经计算了这个

n

，则返回它而不递归”的检查：

cache_mem = {}

def fib(n):
    if n <= 1:
        return n
    elif n in cache_mem:
        return cache_mem[n]

    cache_mem[n] = fib(n - 1) + fib(n - 2)
    return cache_mem[n]


print(fib(933))

注意逻辑是如何基于

n

 工作的，而不是 

n - 1

 和 

n - 2

。让递归调用处理这些情况。担心父框架中的子调用是递归中常见的反模式。

更好的是，使用

@functools.cache

 装饰器来避免必须显式记忆，或避免递归，这是解决此问题的一个糟糕的解决方案（即使使用缓存，它也无法处理 CPython 中大于 ~1k 的 

n

 值，增加开销并使用大量内存）。

Answer 3

在 get 方法中，python 首先计算 fib 函数，然后使用 fib 调用的结果调用 get 方法。不使用默认值方法，首先检查 key 是否存在，如果 true 从 dict 返回，否则评估递归调用