Counting recursive calls of a function

by

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)

More Related Contents:

  1. how to check Recursively if i can create a sum from a list of numbers? [closed]
  2. Why does my recursive function return None?
  3. What is the maximum recursion depth in Python, and how to increase it?
  4. Recursive function returning none in Python [duplicate]
  5. Loop through all nested dictionary values?
  6. Python recursion with list returns None [duplicate]
  7. Basics of recursion in Python
  8. Return in Recursive Function
  9. Python: Maximum recursion depth exceeded
  10. recursive iteration through nested json for specific key in python
  11. Recursion and return statements
  12. python recursion return None type
  13. How to flatten a nested JSON recursively, with flatten_json
  14. Using self.xxxx as a default parameter – Python
  15. Recursive function returning none? [duplicate]
  16. Setting property causes maximum recursion depth exceeded
  17. How to find common elements in list of lists?
  18. python recursive vectorization with timeseries
  19. Python: using a recursive algorithm as a generator
  20. Generate all possible lists of length N that sum to S in Python
  21. How can a recursive regexp be implemented in python?
  22. Recursive diff of two dictionaries (keys and values)?
  23. python recursive function that prints from 0 to n?
  24. Python: maximum recursion depth exceeded while calling a Python object
  25. How do I reverse a list using recursion in Python?
  26. Finding all maze solutions with Python
  27. Recursive Typing in Python 3.5+ [duplicate]
  28. Python Array Rotation
  29. Cross product of sets using recursion
  30. Given a list of elements in lexicographical order (i.e. [‘a’, ‘b’, ‘c’, ‘d’]), find the nth permutation – Average time to solve?

Leave a Comment