decorating recursive functions

Question

I have a decorator that I wrote that will time a given function. It seems to work well with any function, except for recursive functions.

Decorator:

def tictoc(repeats=3, loops=1): def t(func): from functools import partial, wraps import timeit @wraps(func) def timer(*args, **kargs): elapsed = timeit.repeat(partial(func, *args, **kargs), repeat = repeats, number=loops) mine = min(elapsed) print "%s finished in %.5fs (%d loops, %d times) with %.5fs per loop" % (func.__name__, mine, loops, repeats, mine/loops) return timer return t

the recursive function is the basic Fibonacci algorithm.

@tictoc() def fib(i): return ( 0 if i == 0 else 1 if i == 1 else fib(i-1) + fib(i-2) ) fib(15)

The program fails with the following error

fib finished in 0.00000s (1 loops, 3 times) with 0.00000s per loop fib finished in 0.00000s (1 loops, 3 times) with 0.00000s per loop fib finished in 0.00000s (1 loops, 3 times) with 0.00000s per loop Traceback (most recent call last): File "decor.py", line 61, in <module> [fib(x) for x in range(1,50)] File "/home/grout/Dropbox/Python/tictoc.py", line 7, in timer elapsed = timeit.repeat(partial(func, *args, **kargs), repeat = repeats, number=loops) File "/usr/lib/python2.7/timeit.py", line 233, in repeat return Timer(stmt, setup, timer).repeat(repeat, number) File "/usr/lib/python2.7/timeit.py", line 221, in repeat t = self.timeit(number) File "/usr/lib/python2.7/timeit.py", line 194, in timeit timing = self.inner(it, self.timer) File "/usr/lib/python2.7/timeit.py", line 100, in inner _func() File "decor.py", line 59, in fib fib(i-1) + fib(i-2) ) TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

What I don't understand is how the decorator executes a few times and then fails. Any help would be appreciated.

Claudiu · Accepted Answer · 2011-05-02 17:32:46Z

6

The function your decorator returns doesn't return anything. So although fib is supposed to return an integer, your wrapped fib returns None. It works a few times because a few recursive calls are made without checking the results of fib, but when it needs the result (when it has to add two of them together) you get the exception.

answered May 2, 2011 at 17:32

Claudiu

231k174 gold badges507 silver badges701 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

iform Over a year ago

thanks for pointing this out. However, I run into another problem. The decorator now times each individual function call and prints the results to the stdout. I would rather time each call silently and return a cumulative time. However, I am at a loss how implement this. Any suggestions?

iform Over a year ago

I think that adding each runtime to a list (timeit.repeats returns a list), then returning min(min(cumulative_times)) would be the way to do it.

Claudiu Over a year ago

just do something like: "start=time.time(); for i in xrange(repeat): func(*args,**kwargs); time_taken=time.time()-start"

iform · Accepted Answer · 2011-05-04 22:58:42Z

I think I am going to settle on this

def tictoc(func, repeats=3, loops=100, *args, **kargs): elapsed = timeit.repeat(lambda: func(*args, **kargs), repeat = repeats, number = loops) mine = min(elapsed) return "%s finished in %.5fs (%s loops, repeated %s times): %.5fs best time per loop" %(func.__name__, mine, loops, repeats, mine/loops)

Collectives™ on Stack Overflow

decorating recursive functions

2 Answers 2

3 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Related