斐波那契数列/兔子数列/台阶问题（关键词：）

0, 1, 1, 2, 3, 5, 8, 13......

递归算法：

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

递归算法 - pythonic（不考虑 n 等于 0 的情况）：

def fib_recur1(n):
        if n == 0:
                return 0
        return 1 if 1<= n <= 2 else fib_recur2(n-1) + fib_recur2(n-2)

递归算法改进 - 使用备忘录缓存

def fib_recur2(n):
        global cache
        cache = {0:0, 1:1, 2:1}

        if n not in cache.keys():
                cache[n] = fib_recur2(n-2) + fib_recur2(n-1)

        return cache[n]

递归算法改进 - 使用备忘录缓存 - 使用装饰器

def memo1(func):
        cache = {}
        def wrapper(arg):
                if arg not in cache.keys():
                        cache[arg] = func(arg)
                return cache[arg]
        return wrapper

fib_recur1 = memo1(fib_recur1)

递归算法改进 - 使用备忘录缓存 - 使用装饰器 - 改进装饰器

上面的算法中，用装饰器装饰完函数以后，无法正确地获取到原函数的函数名称和帮助信息：

>>> fib_recur1 = memo1(fib_recur1)
>>> fib_recur1.__name__
'wrapper'

为了获取这些信息，我们需要使用@functool.wraps：

from functools import wraps

def memo2(func):
        cache = {}
        @wraps(func)
        def wrapper(arg):
                if arg not in cache.keys():
                        cache[arg] = func(arg)
                return cache[arg]
        return wrapper

fib_recur1 = memo(fib_recur1)

非递归算法

def fib_iter(n):
        first, second = 0, 1

        for _ in range(n):
                first, second = second, first+second

        return first

图解：

测试

def test(func):
        lyst = []
        for index in range(0, 8):
                lyst.append(func(index))

        assert lyst == [0,1,1,2,3,5,8,13]
        print(func.__name__, 'pass!')


if __name__ == '__main__':
        funcs = [fib_recur0, fib_recur1, fib_recur2, memo1(fib_recur1), \
                memo2(fib_recur1), fib_iter]

        for func in funcs:
                test(func)

结果：

$ python3 t.py
fib_recur0 pass!
fib_recur1 pass!
fib_recur2 pass!
wrapper pass!
fib_recur1 pass!
fib_iter pass!

参考文献：

1. https://github.com/taizilongxu/interview_python#1-台阶问题斐波那契。