Python decorator to time recursive functions

  • A+
Category:Languages

I have a simple decorator to track the runtime of a function call:

def timed(f):     def caller(*args):         start = time.time()         res = f(*args)         end = time.time()         return res, end - start     return caller 

This can be used as follows, and returns a tuple of the function result and the execution time.

@timed def test(n):     for _ in range(n):         pass     return 0  print(test(900)) # prints (0, 2.69e-05) 

Simple enough. But now I want to apply this to recursive functions. Applying the above wrapper to a recursive function results in nested tuples with the times of each recursive call, as is expected.

@timed def rec(n):     if n:         return rec(n - 1)     else:         return 0  print(rec(3)) # Prints ((((0, 1.90e-06), 8.10e-06), 1.28e-05), 1.90e-05) 

What's an elegant way to write the decorator so that it handles recursion properly? Obviously, you could wrap the call if a timed function:

@timed def wrapper():     return rec(3) 

This will give a tuple of the result and the time, but I want all of it to be handled by the decorator so that the caller does not need to worry about defining a new function for every call. Ideas?

 


The problem here isn't really the decorator. The problem is that rec needs rec to be a function that behaves one way, but you want rec to be a function that behaves differently. There's no clean way to reconcile that with a single rec function.

The cleanest option is to stop requiring rec to be two things at once. Instead of using decorator notation, assign timed(rec) to a different name:

def rec(n):     ...  timed_rec = timed(rec) 

If you don't want two names, then rec needs to be written to understand the actual value that the decorated rec will return. For example,

@timed def rec(n):     if n:         val, runtime = rec(n-1)         return val     else:         return 0 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: