python - Counting recursive calls of a function

Question

I have recursive code for generating 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 the 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

Counter code:

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

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)