实现fibonacci序列的5种Python方式

看到一篇介绍python实现fibonacci的计算方式，觉得甚是有趣，相信绝大多数人最初开始学习编程的时候，都是用的递归实现，即以下的示例2；然后了解掌握记忆术，即示例4和5，python中的记忆术可以用装饰器实现，或者functools里面的lru_cache函数实现；然后才是动态规划的示例1；学习到了Python之后，才知道可以用生成器实现，即示例3。

第六个使用标准库的方法是我自己加的，这个方法要注意使用，可能会有缓存保存，如果有必要需要清除。

## Example 1: Using looping technique
def fib(n):
 a,b = 1,1
 for i in range(n-1):
  a,b = b,a+b
 return a
print fib(5)
 
## Example 2: Using recursion
def fibR(n):
 if n==1 or n==2:
  return 1
 return fibR(n-1)+fibR(n-2)
print fibR(5)
 
## Example 3: Using generators
a,b = 0,1
def fibI():
 global a,b
 while True:
  a,b = b, a+b
  yield a
f=fibI()
f.next()
f.next()
f.next()
f.next()
print f.next()
 
## Example 4: Using memoization
def memoize(fn, arg):
 memo = {}
 if arg not in memo:
  memo[arg] = fn(arg)
  return memo[arg]
 
## fib() as written in example 1.
fibm = memoize(fib,5)
print fibm
 
## Example 5: Using memoization as decorator
class Memoize:
 def __init__(self, fn):
  self.fn = fn
  self.memo = {}
 def __call__(self, arg):
  if arg not in self.memo:
   self.memo[arg] = self.fn(arg)
   return self.memo[arg]
 
@Memoize
def fib(n):
 a,b = 1,1
 for i in range(n-1):
  a,b = b,a+b
 return a
print fib(5)

# Example6: using functools's lru_cache
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
       if n < 2:
            return n
        else:
            return fib(n-1) + fib(n-2)

下面是对于以上算法的总结：
https://technobeans.com/2012/04/19/5-ways-of-fibonacci-in-python-best-way/