CODEWITHSUNDEEP
pythonrecursion
snow
snow

Reputation: 73

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

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)

Upvotes: 7

Views: 11275

Answers (5)

martineau
martineau

Reputation: 123473

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)

Upvotes: 4

Mike Vella
Mike Vella

Reputation: 10575

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)

Upvotes: 6

DSM
DSM

Reputation: 353089

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.

Upvotes: 10

loopbackbee
loopbackbee

Reputation: 23322

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)

Upvotes: 7

Scott Hunter
Scott Hunter

Reputation: 49803

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.

Upvotes: 0

Related Questions