如何查找递归函数中的减法次数

Question

这是代码：

def f(k):
    if k<3:
        return 1
    return f(k-1)+f(k-2)+f(k-3)

提前致谢！

Answer 1

您可以编写一个装饰器来计算对该函数的调用：

def count(func):
    def wrapper(*args, **kwargs):
        if kwargs.pop("reset", False):
            wrapper.calls = 0
        wrapper.calls += 1
        return func(*args, **kwargs)
    wrapper.calls = 0
    return wrapper
    
@count
def f(k):
    if k<3:
        return 1
    return f(k-1)+f(k-2)+f(k-3)

现在您可以计算函数调用数：

>>> f(5, reset=True)
9
>>> f.calls
13
>>> f(23, reset=True)
532159
>>> f.calls
798251