fibonacci.py

#from functools import lru_cache#python >=3.2
from functools32 import lru_cache#python 2.7
#from repoze.lru import lru_cache#python 2.7

#NOTE: you can use python -m trace --count fibonacci.py
#to see how many times each instruction is called

#@lru_cache(maxsize=500)#repoze.lru needs maxsize arg
@lru_cache()#using functools32
def fibonacci(n):
    if n<=1:
        return n
    return fibonacci(n-1)+fibonacci(n-2)
print(fibonacci(100))

#manual dynamic programming way
#cache ={0:0,1:1}
#def fibonacci(n):
#    if n in cache:
#        return cache[n]
#    cache[n] = fibonacci(n-1)+fibonacci(n-2)
#    return cache[n]