当字典在函数中时，为什么我的斐波那契需要这么长时间？

Question

在这里，我有一些代码可以返回斐波那契数字的最后一位。当我将缓存字典放置在函数中时，程序对于小n正常工作。当我尝试更大的n（例如300）时，该程序将永远耗费时间。但是，当使字典成为全局字典时，会得到一个较大的n（例如300）的即时结果。是什么导致在函数中声明的字典与函数外部声明的字典之间如此大的性能差异？

def fib_last_digit_mem(n):
    cache = {}

    if n in cache:
        return cache[n]

    if(n <= 1):
        return n

    fib = (fib_last_digit_mem(n-1) + fib_last_digit_mem(n-2))%10
    cache[n] = fib
    return fib

Answer 1

由于这是递归函数，如果您在函数内部实例化了缓存，则每次函数递归时都会再次实例化它。这也意味着缓存始终为空，因此您绝不会走短路if n in cache