CODEWITHSUNDEEP
pythonrecursion
MAPython
MAPython

Reputation: 51

Counting recursive calls of a function

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)

Upvotes: 5

Views: 7645

Answers (3)

ggorlen
ggorlen

Reputation: 56965

You can write a decorator for the function you want to track calls on. When the decorator function is called, it increments its internal call count, passes arguments to the tracked function and returns the decorated function's result to its caller.

This way, there's no need to make any adjustments to the function's internals, parameters or return type or use globals--just decorate and roll.

import functools


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

    wrapper.calls = 0
    return wrapper


if __name__ == "__main__":

    @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

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

Upvotes: 1

hiro protagonist
hiro protagonist

Reputation: 46859

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)

Upvotes: 10

Tadhg McDonald-Jensen
Tadhg McDonald-Jensen

Reputation: 21453

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)

Upvotes: 5

Related Questions