Tracking the number of recursive calls without using global variables in Python

Question

How to track the number of recursive calls without using global variables in Python. For example, how to modify the following function to keep track the number of calls?

def f(n):
    if n == 1:
        return 1
    else:
        return n * f(n-1)

print f(5)

Answer 1

As delnan said, if you want all calls ever, it's impossible without a global, so I'm assuming you just want the call depth, for which you just need to add a return value

def f(n):
    if n == 1:
        return 1,0
    else:
        x, call_depth= f(n-1)
        return n * x, call_depth+1

If you're dealing with several recursive calls, you can do a max(call_depth1, call_depth2) (depth of longest call tree) or just sum the two (total number of actual calls)

Answer 2

Here's a neat trick that doesn't use a global: you can stash the counter in the function itself.

def f(n):
    f.count += 1
    if n == 1:
        return 1
    else:
        return n * f(n-1)

After which:

>>> f.count = 0 # initialize the counter
>>> f(5)
120
>>> f.count
5
>>> f(30)
265252859812191058636308480000000L
>>> f.count
35

This handles the "all calls ever" case, anyhow.

Answer 3

This method will give you the total number of times the function has run:

def f(n):
    if hasattr(f,"count"):
        f.count += 1
    else:
        f.count = 1
    if n == 1:
        return 1
    else:
        return n * f(n-1)

Answer 4

Here's a way that uses the stack instead of global variables. As shown it tallies the number of calls to the function including the initial one, not just the number of recursive calls the function made to itself. To make it do that, just move the ncalls += 1 to the beginning of the else statements.

def f(n, ncalls=0):
    ncalls += 1
    if n == 1:
        return 1, ncalls
    else:
        res, ncalls = f(n-1, ncalls)
        return n * res, ncalls

for n in xrange(1, 6):
    print 'f({}): {:4d} ({} calls)'.format(n, *f(n))

Output:

f(1):    1 (1 calls)
f(2):    2 (2 calls)
f(3):    6 (3 calls)
f(4):   24 (4 calls)
f(5):  120 (5 calls)

Answer 5

You could add an argument to keep count of the calls in (would need to be something mutable), where it gets incremented at the start of the function.