计算函数的递归调用 [英] Counting recursive calls of a function

问题描述

我有一个加泰罗尼亚数字的递归代码.我设法编写了递归调用，但由于某种原因计数器无法正常工作.例如，呼叫第 7 加泰罗尼亚号码的次数应为 1215.返回值需要是加泰罗尼亚数字和调用次数的元组，例如:(429,1215).原始代码:

I have a recursive code of the catalan numbers. I managed to write the recursive call, but for some reason the counter is not working properly. for example, the number of calls for 7th catalan number should be 1215. the return value needs to be a tuple of the catalan number and the number of calls,for example: (429,1215). original code:

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)

提前致谢！

推荐答案

python 允许您将变量(以下代码段中的catalan.counter)附加到函数对象，这样您就不会必须一直传递计数器并且不需要全局变量:

python allows you to attach a variable (catalan.counter in the snippet below) to the function object, so you don't have to pass the counter along all the time and don't need a global variable:

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;但这当然违背了计算函数被调用次数的目的；你只能得到调用函数的编号，带有 unique n.

and seeing that the function is called several times with the same arguments: for more efficiency you could use the lru_cache; but this of course defeats the purpose of counting how many times the function was called; you'd only get the number the function was called with a unique n.

from functools import lru_cache

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

    ...

<小时>

这可能有点题外话...但如果您需要具有单独计数器的函数的单独实例，请使用 闭包 可能正是您所需要的:

---

this may be a bit off-topic... but in case you need separate instances of the function with separate counters, a closure might be just what you need:

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)

这篇关于计算函数的递归调用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！