一般计算fibonacci的方法：
1 def fibonacci (n): 2 if n == 0 or n == 1: 3 return 1 4 else: 5 return fibonacci(n-1) + fibonacci(n-2)
这样的 call graph for fibonacci with n=4:
当计算 fibonacci(30)的时候还可以，当计算 fibonacci(50)的时候就很慢了。
好的方法是：用dict记录下来之前计算过的值。
A previously computed value that is stored for later use is called a hint.
好的方法是：
previous = {0:1, 1:1}
def fibonacci(n):
if previous.has_key(n):
return previous[n]
else:
newValue = fibonacci(n-1) + fibonacci(n-2)
previous[n] = newValue
return newValue
这样就很快了。
类似的计算阶乘：
previous = {1:1,2:2}
def n(i):
if previous.has_key(i):
return previous[i]
else:
newValue = i*n(i-1)
previous[i] = newValue
return previous[i]
---How to Think Like a Computer Scientist（Learning with Python）
原文：http://www.cnblogs.com/eagle-chen/p/4260744.html