memoize.py

def fact(n):
	if (n <= 0):
		return 0
	elif ( n < 3 ):
		return n 
	else:
		return fact(n-1) + fact(n-2)


def memoize(f):
	cache = dict()
	def g(n): 
		if (n in cache):
            return cache[n]
		cache[n] = f(n)
		return cache[n]

	def h(n):
		return g(n-1) + g(n-2)
	return h


#######
def memo(func):
    cache = {}
    def helper(*args):
        if args in cache:
            return cache[args]
        else:
            cache[args] = func(*args)
            return cache[args]
    return helper

def timeFunc(func):
    start = time()
    func(x)
    print time() - start
    
@timeFunc       
@memo    
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)
        
@memo
def binomial(n,k):
    if k == 0 or n == k:
        return 1
    elif k == 1:
        return n
    else:
        return binomial(n-1, k) + binomial(n-1, k-1)