# Fibonacci with a memoization decorator

Decided to read Higher Order Perl today.. It talked about using a recursive function to calculate the Fibonacci sequence.. Then talked about the run time it took for large calls and how to reduce that.

For example (in python though)

`import collectionsimport timeitcounter = collections.Counter()`
`cache = {}`
`def fib(n):    if n <= 2:        return n    counter[n-1] +=1    counter[n-2] +=2    return fib(n-1) + fib(n-2)`
`fib(35)print counter.most_common()`

This results in a lot of repeated calculations. For instance, fib(2) is calculated 7,881,196 times!

`fib(2) 14930352`
`[(2, 7881196), (1, 7049156), (3, 4870847), (4, 3010349), (5, 1860498), (6, 1149851), (7, 710647), (8, 439204), (9, 271443), (10, 167761), (11, 103682), (12, 64079), (13, 39603), (14, 24476), (15, 15127), (16, 9349), (17, 5778), (18, 3571), (19, 2207), (20, 1364), (21, 843), (22, 521), (23, 322), (24, 199), (25, 123), (26, 76), (27, 47), (28, 29), (29, 18), (30, 11), (31, 7), (32, 4), (33, 3), (34, 1)]`
`real 0m9.139s user 0m9.046s sys 0m0.042s`

#### Memoization

But with memoization/caching or whatever you call it, you only have to calculate each value once.

`def _fib(n):    if n <= 2:        return n    if cache[n]:        return cache[n]        cache[n-1] = _fib(n-1)    cache[n-2] = _fib(n-2)    return cache[n-1] + cache[str(n-2)]`

Look ma, I can fib large numbers.

`About to _fib(999) 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875`
`real 0m0.056s user 0m0.020s sys 0m0.020s`

But apparently this is not the pythonic way according to SO. The pythonic way is to create a decorator for memoization.

#### Memoization Decorator

There are a lot of different memoization functions, if you want to go down that rabbit hole.

``def memoize(f):    cache = {}    def decorated_function(*args):        if args in cache:            return cache[args]        else:            cache[args] = f(*args)            return cache[args]    return decorated_function``
`#This decorates the function to use a cache! Woohoo@memoizedef fib(n):    if n ==0:        return 0    if n <= 2:        return 1    return fib(n-1) + fib(n-2)`

Execution time for time for fib(40) = 26 seconds, but _fib(40) =.036ms

### Resources:

http://ujihisa.blogspot.com/2010/11/memoized-recursive-fibonacci-in-python.html

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.