[Tutor] fibonacci [caching]

[Danny Yoo]

> def fib2(n):
>     if n < 2:
>         return n
>     else:
>         return fib2(n-2) + fib2(n-1)

Hi Gregor,


The above defintion of the fibonacci function is always used as the
prototypical example of abusive recursion.  However, there is a
programming technique called "caching" that will greatly improve the
performance of something like the recursive fibonacci function.


###
"""Demonstration of a simple caching technique."""

import weakref

class Cache:
    def __init__(self, f):
        self.f = f
        self.cache = {}

    def __call__(self, *args):
        if not self.cache.has_key(args):
            self.cache[args] = self.f(*args)
        return self.cache[args]

def fib2(n):
    if n < 2:
        return n
    return fib2(n-2) + fib2(n-1)

fib2 = Cache(fib2)
###



Let's see how this might work:

###
>>> def measureFib(n):
...     start = time.time()
...     result = fib2(n)
...     stop = time.time()
...     print "fib2(%s) == %s, taking %s" % (n, result, stop-start)
...
>>> measureFib(100)
fib2(100) == 354224848179261915075, taking 0.00286304950714
>>> measureFib(100)
fib2(100) == 354224848179261915075, taking 4.19616699219e-05
###



This version of fib2() performs much better than the original; in fact,
it's almost as fast as the iterative solutions!  (Although it does take up
more space.)  So for this specific example, at least, there are perfectly
good ways to get excellent performance as well as clean code.


This technique of caching is often called "memoization", and there's a
reference to it in the Python Cookbook:

    http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52201



Hope this helps!