如何跟踪斐波纳契中每个元素的计算次数？

Question

这是给定的斐波那契数列：

1,1,2,3,5,8,13,21

这意味着n =8。这是我的斐波那契代码：

def fib(n, count= 0):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n-1) + fib(n-2)

如何创建一个函数来计算上述序列中每个元素的计算次数？例如，在计算fib（5）时，fib（0）被调用3次，fib（1）被调用5次，fib（2）被调用3次，依此类推...

我尝试使用全局计数器，但我意识到每个n值都应该有一个计数器（如果我输入错了，请更正我）。任何帮助将不胜感激。

Answer 1

要计算您使用给定调用函数的次数，n可以创建一个Counter并递增它：

from collections import Counter
c = Counter()

def fib(n):
    c[n] += 1
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n-1) + fib(n-2)

fib(8)
print(c)
# Counter({1: 21, 2: 13, 0: 13, 3: 8, 4: 5, 5: 3, 6: 2, 8: 1, 7: 1})

这也是查看记忆该功能效果的好方法。例如，这是使用的计数lru_cache：

from collections import Counter
from functools import lru_cache

c = Counter()

@lru_cache()
def fib(n):
    c[n] += 1
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n-1) + fib(n-2)

fib(8)
print(c)
#Counter({8: 1, 7: 1, 6: 1, 5: 1, 4: 1, 3: 1, 2: 1, 1: 1, 0: 1})