Using caching (pseudo dynamic programming) to remove all the redundant calls of a regular recursive Fibonacci program.

fast_fib.py

"""Calculate the Fibonacci sequence caching the 
values after each call.
"""

dp = {}
dp[0] = 0
dp[1] = 1

def fib(n):
	
	# Check for the value, calculate if it's not there
	try:
		value = dp[n]
	except KeyError:
		value = fib(n-1) + fib(n-2)
		dp[n] = value
	
	return value
	
	# Old way
	#return fib(n-1) + fib(n-2)
	
print fib(40)