引言 #
递归是高度抽象化问题的一个好东西，我们能从很多算法书里面看到这个，
但是递归虽然对于人来说好理解，但是计算机执行起来会损失性能，一个差的递归可能会耗光计算机的资源
接下来我们来看一个非常经典的算法问题Fibonacci数
f(n) = n (n < 2)
f(n) = f(n-1) + f(n-2) (n >= 2)
我们可以很轻松的用递归解决掉它
def fibonacci(n):
if n < 2:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
当n比较小的时候很快就出结果了，但是当n大于100时候要很久才能出结果，如果n大于1000，直接报出超出迭代深度的错误（python默认迭代深度是1000）
现在我们来解决两个问题
- 为什么
n大于100时候就很久才能算出结果 - 为什么
n大于1000就报迭代深度的错误
首先我们要知道一个概念就是堆栈段，每个进程开始运行时都会初始化一个堆栈段，这在物理上就是一小块内存，初始化堆栈段的时候计算机要做一些看起来同程序毫无关系的事情，比如说将寄存器的值推入堆栈里面等等
当你在运行主程序的时候你调用一个子函数，系统又会在当前堆栈段新建一个堆栈段，你子程序运行完了后会删掉这个堆栈段回到主程序，但是递归有个问题，就是他调用子程序的时候不会立即返回又会再调用自己
没办法因为子程序还没返回，所以计算机又初始化一个堆栈段，一个n为10的fibonacci函数就会初始化掉 2 ** 10 = 1024个堆栈段，n越大值会指数型增长，虽然1000个初始化在当今计算机上发不了多少时间，但是当我们n大于20就要 百万次初始化了
这就是为什么n很大的时候要很久才能算出结果，在一些单片机上面，循环调用空函数就是延时的功能，原理也就是堆栈初始化耗时间，而且不但耗时间假如像递归这样调用上百万次初始化而不返回将会耗掉大量内存在堆栈段上。
对策 #
要解决这两个问题，一种方法是改算法，使用非递归算法，这个网上有很多，感兴趣的可以去搜一下，第二种是使用协程解决递归问题
如何使用协程来解决递归呢我们先改主程序，将return换成yield
def _fibonacci(n):
if n < 2:
yield n
else:
yield ( (yield (_fibonacci(n-1)) + (yield (_fibonacci(n-2)))
接下啦我们运行一下函数
>>> _fibonacci(10)
<generator object _fibonacci at 0x00000013A74779E8>
没有返回结果,返回一个生成器，那我们用list简单的试一下吧
>>> list(_)
......
......
TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'
生成器小知识 #
这里补充几点生成器的知识，懂得可以跳过
生成器大家都用过，无论是Python2或Python3都不陌生,最简单的生成器是这种
>>> items = ( x for x in range(10))
我们一般搭配for来使用
>>> for i in items:
... print(i)
...
我们也可以用协程来实现这个生成器
def iter_func(n):
for i in range(n):
yield n
像上面一样使用for就能实现一样的功能，在这个例子里面yield好像变成了一个return的作用，在for语句中，随着每次请求都会return一个数过来
在这个里面yield好像就是这么个功能，但是yield的作用远远不止于此
我们现在来改一下这个函数
def iter_func(n):
for i in range(n):
r = yield i
print('result', r)
我们用list来运行一下这个函数
>>> list(iter_fun(2))
0
result None
1
result None
r返回了一个None，我们尝试自己实现一下for循环,有两种方式
- next(generator)
- generator.send(msg)
先尝试用next
>>> it = iter_fun(2)
>>> next(it)
0
>>> next(it)
result None
1
我们介绍一下next函数, next接受两个参数，第一个是生成器，第二个是返回的默认值,next函数在这里相当于下面这个函数
def next(iterator, default=None):
try:
iterator.send(None)
except StopIteration:
if default:
return default
else:
raise StopIteration()
为什么第二个执行了print函数而第一个没有执行?
生成器工作原理 #
这里我们介绍一下生成器的工作原理
当我们使用调用一个函数的时候，一般是碰到return或者执行全部函数就会返回父函数
但是生成器不同，假如他执行函数碰到yield，他就会直接返回一个生成器。
这个生成器我们可以把它看做是邮递员，我们必须写好目的地,他才会帮我们把信寄出去。
现在我们分析一下生成器的具体流程，我们先定义一个简单的生成器
def mygenerator(n):
while True:
r = yield n
n -= 1
print('result', r)
然后我们调用这个生成器
>>> i = mygenerator(10)
>>> i
<generator object mygenerator at 0x7f420a339d00>
我们得到一个生成器，我们先尝试发送一个地址给“邮递员”
>>> i.send(0)
...
TypeError: can't send non-None value to a just-started generator
我们得到一个错误，必须传递一个None，我们先不管，先送一个None值过去
>>> i.send(None)
10
我们得到一个10，再送一个地址过去
>>> i.send(None)
result None
9
我们现在来分析一下代码，第一次调用的时候直接返回了，第二次调用我们从r = yield n那行开始执行，并且运行到第二个r = yield n那里停止了
就可以解释上面为什么要第一次传递None过去，因为第一次调用它会直接返回yield后面的值给我们，第二次调用 我们可以根据第一次生成器递给我们的值，决定我们第二次想寄的“信”，因为第一次传递过去“信”并不能被处理，所以Python强制我们传递一个None值过去
我们回到上面的函数
def _fibonacci(n):
if n < 2:
yield n
else:
yield ( (yield (_fibonacci(n-1)) + (yield (_fibonacci(n-2)))
我们来分析一下流程，为了解决上面的问题我们先把函数简化，去掉递归
def f(n):
yield (yield n) + (yield n - 1)
我们先创建一个生成器i
>>> i = f(5)
>>> i
<generator object f at 0x7f4a421d8f10>
我们先启动i
>>> i.send(None)
5
我们再把得到5传给i
>>> i.send(5)
4
我们得到yield n -1返回的4，我们再把4传给i，得到最终结果
>>> i.send(5)
9
假如我们把后面两个send的值换成其他值我们会得到不同的结果，这里我们可以看到我们，要实现上面函数必须要依靠一个栈，保存我们返回的生成器，然后依次调用生成器返回结果，具体代码如下
def fibonacci(n):
stack = [ _fibonacci(n)]
last_result = None
while stack:
last = stack[-1]
try:
if isinstance(last, types.GeneratorType):
stack.append(last.send(last_result))
last_result = None
else:
last_result = stack.pop()
except StopIteration:
stack.pop()
return result
我们这里用stack作为我们的堆栈，用last_result保存上一个生成器返回的值
总结 #
我们使用协程解决掉了递归错误，但是这个方法并不可以给我们算法加速，虽然n为1000以上不会报递归错误，但是等待的时间还是很长很长。。。
虽然协程在这个方法里面并没有起到多大作业，协程在算法方面还是没有太多帮助，协程在计算机I/O还有网络请求方面有更好的效率，但是这次尝试让我们对协程如何使用有了一个清晰的了解
有兴趣的可以去了解一下协程在异步网络请求的应用