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)
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.
f.count a global too, by definition? Is this better than passing a reference in a argument, somehow?
count isn't in globals(), so there's certainly a defensible definition of "global" which makes it not one. @MikeVella: I'm not a fan of hacking function attributes myself, and would never use it in production code, but I find f.count = 0 the least confusing part of this. I certainly find it less ugly than the hasattr checks I would need otherwise, but beauty is in the eye of the beholder, I guess.
f.count is an attribute of the global variable f (which is the function object), so it's not entirely clear that doing it this way satisfies the requirement of not using a global variables.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)
f(3) then another line with f(4), that you want the total number from each of these two calls added together.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)
f() will count correctly. You should probably reset the attribute before returning 1.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)
n is only true for this particular example. So I prefer your original answer better.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.
