计算函数的递归调用次数

Question

我有生成加泰罗尼亚数字的递归代码。

我设法编写了递归调用，但由于某些原因，计数器无法正常工作。

例如，第7个加泰罗尼亚号码的呼叫数应为1215。

返回值需要是加泰罗尼亚号码和调用次数的元组，例如：(429,1215)。

原始代码：

def catalan_rec(n):
    if n<=1:
        return 1
    res=0
    for i in range(n):
        res+=catalan_rec(i)*catalan_rec(n-i-1)
    return res

计数器代码：

def catalan_rec_count(n,counter=1):
    if n<=1:
        return 1
    res=0
    for i in range(n):
        res+=catalan_rec_count(i,counter+1)*catalan_rec_count(n-i-1,counter+1)        
    return (res,counter)

Answer 1

python允许您将变量(下面代码片段中的catalan.counter)附加到函数对象，因此您不必一直传递计数器，也不需要全局变量：

def catalan(n):

    catalan.counter += 1

    if n <= 1:
        return 1
    res = 0
    for i in range(n):
        res += catalan(i) * catalan(n-i-1)
    return res

catalan.counter = 0

print(catalan(5))
print(catalan.counter)

看到函数被多次调用，并使用相同的参数:为了获得更高的效率，您可以使用lru_cache；但这当然违背了计算函数被调用的次数的目的；您只能通过一个唯一的n获得函数被调用的次数。

from functools import lru_cache

@lru_cache(maxsize=128)
def catalan(n):

    ...

这可能有点离题...但是，如果您需要具有单独计数器的函数的单独实例，则closure可能正是您所需的：

def make_catalan():

    counter = 0

    def catalan(n):

        nonlocal counter
        counter += 1
        catalan.counter = counter

        if n <= 1:
            return 1
        res = 0
        for i in range(n):
            res += catalan(i) * catalan(n-i-1)
        return res

    return catalan

catalan_1 = make_catalan()
print(catalan_1(2))
print(catalan_1.counter)

catalan_2 = make_catalan()
print(catalan_2(3))
print(catalan_2.counter)

Answer 2

您需要分离res+=catalan_rec_count(i,counter+1)*catalan_rec_count(n-i-1,counter+1)行，以便它可以分别对递归结果和计数器执行操作，因此只需将它拆分为几个额外的行，而且在这种情况下，您不会将counter+1传递给递归调用，以便它跟踪独立于当前帧的调用。

def catalan_rec_count(n,counter=1):
    if n<=1:
        return (1, counter) #remember to return the counter in this case too!
    res=0
    for i in range(n):
        #get the recursive results and counters for both calls
        #don't pass counter+1 to it, it should count how many times it is called on it's own
        partial1, inner_c1 = catalan_rec_count(i)
        partial2, inner_c2 = catalan_rec_count(n-i-1)
        #apply the logic with the actual result and add to the counter
        res+=partial1*partial2
        counter+= inner_c1 + inner_c2
    return (res,counter)

Answer 3

您可以设置一个类的实例，该类为要跟踪其调用的函数提供一个计数器和一个装饰器方法。当装饰器函数被调用时，它会递增计数并将参数传递给被跟踪的函数。

这样，就不需要对函数的内部结构、参数、返回类型或使用全局变量进行任何调整--只需修饰和滚动即可。

import functools

class CallCounter:
    def __init__(self):
        self.call_count = 0

    def count_calls(self, fn):
        @functools.wraps(fn)
        def wrapper(*args, **kwargs):
            self.call_count += 1
            return fn(*args, **kwargs)
    
        return wrapper

if __name__ == "__main__":
    call_counter = CallCounter()
    @call_counter.count_calls
    def catalan_rec(n):
        if n<=1:
            return 1
        res=0
        for i in range(n):
            res+=catalan_rec(i)*catalan_rec(n-i-1)
        return res
    
    # or without a decorator:
    #call_counter = CallCounter()
    #catalan_rec = call_counter.count_calls(catalan_rec)

    print(catalan_rec(n=7)) # => 429
    print(call_counter.call_count) # => 1215