python - 如何计算一个值在递归函数中出现的次数？

Question

如果您有递归函数(例如斐波那契数列):

def fib(n):
    """Return Fibonacci of n; assumes n is an int >= 0."""
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

例如，当调用 fib(20) 时，如何计算 fib(2) 发生的次数？

Answer 1

你可以使用装饰器:

import functools

def count(f):
    """Count function calls."""
    @functools.wraps(f)
    def counted(*args, **kwargs):
        counted.count_calls += 1
        return f(*args, **kwargs)
    counted.count_calls = 0
    return counted

fib = count(fib)
fib(5)
fib.count_calls
# 15

或者，您现在可以使用此装饰器和 @ 符号在任何函数定义之前添加:

@count
def fib(n):
    ...

fib(5)
fib.count_calls
# 15

注意，这个装饰器会累积函数调用:

fib(5)
fib(5)
fib.count_calls
# 30

这是一个巧妙的实现，利用了鲜为人知的 function attributes .请注意，原始装饰器是从 John DiNero 在他的 lecture on Memoization 中讨论的 count 函数修改而来的。他在其中解决了这个具体问题。