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)

Answer 2

You need to seperate out the line res+=catalan_rec_count(i,counter+1)*catalan_rec_count(n-i-1,counter+1) so that it can do operations with the recursive results and the counters seperately, so just split it up into a few extra lines, also in this case you wouldn't pass counter+1 to the recursive calls so that it tracks it's calls independant to the current frame..

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)