计算函数的递归调用

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):

    ...

这可能有点偏离主题......但是如果您需要使用单独的计数器的函数的单独实例,闭包可能正是您所需要的:

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)