无限“递归”的python程序

- 日理万妓 2022-06-18 08:52 219阅读 0赞

如果一个函数直接或者间接调用了自己，那么就形成了递归（recursion），比如斐波那契数列的一个实现

def fib(n):
        if n <= 2:
            return 1
        else:
            return fib(n - 1) + fib(n - 2)

递归一定要有结束条件，否则就形成了死循环， 比如下面的例子：

![复制代码][copycode.gif]

def a():
        b()
    def b():
        a()
     
    if __name__ == '__main__':
        a()

![复制代码][copycode.gif]

很快 就会抛出一个异常： RuntimeError: maximum recursion depth exceeded

会什么报这个异常，很简单，我们都知道子程序调用（call）需要压栈出栈，如果无限递归调用，那么就一直压栈，没有出栈，内存消耗也越来愈多。python比较高级，直接抛出这个异常，结束程序运行。

[前面的文章][Link 1]提到协程（coroutine）这个概念，不管是generator还是greenlet，语法看起来都很像函数调用，但事实上并不是，协程只是在切换的时候把当前调用栈中的信息存储了起来：

> “all local state is retained, including the current bindings of local variables, the instruction pointer, and the internal evaluation stack. When the execution is resumed by calling one of the generator’s methods, the function can proceed exactly as if the `yield` expression was just another external call.”

利用协程实现无限递归似乎成为了可能， 维基百科上有伪代码描述。首先对于greenlet，实现这个“无限递归”函数比较容易的。

![复制代码][copycode.gif]

1 from greenlet import greenlet
     2 def test1():
     3     while True:
     4         z = gr2.switch('msg from test1')
     5         print('test1 ', z)
     6 
     7 def test2(v):
     8     while True:
     9         u = gr1.switch('msg from test2')
    10         print('test2 ', u)
    11 
    12 if __name__ == '__main__':
    13     gr1 = greenlet(test1)
    14     gr2 = greenlet(test2)
    15     print gr1.switch()

![复制代码][copycode.gif]

接下来用generator来模拟这个实现

![复制代码][copycode.gif]

def consumer(func):
        def wrapper(*args,**kw):
            gen = func(*args, **kw)
            gen.next()
            return gen
        wrapper.__name__ = func.__name__
        wrapper.__dict__ = func.__dict__
        wrapper.__doc__  = func.__doc__
        return wrapper
    
    @consumer
    def test1():
        while True:
            data = yield
            print('test1 ', data)
            gr2.send('msg from test1')
    
    @consumer
    def test2():
        while True:
            data = yield
            print('test2 ', data)
            gr1.send('msg from test2')
    
    gr1 = test1()
    gr2 = test2()
    
    gr1.send("init")

![复制代码][copycode.gif]

运行报错：ValueError: generator already executing，这个错误在[这篇文章][Link 1]也有提到，这个问题，在[维基百科][Link 2]上正确的姿势。我们改改代码

![复制代码][copycode.gif]

def test1():
        while True:    
            data = yield (gr2, 'msg from test1')
            print('test1 ', data)
            
    def test2():
        while True:
            
            data = yield (gr1, 'msg from test2')
            print('test2 ', data)
            
    gr1 = test1()
    gr2 = test2()
    gr1.next()
    gr2.next()
    def run():
        co, data = gr1, 'init'
        while True:
            co, data = co.send(data)
    run()

![复制代码][copycode.gif]

This‘s Ok！

[copycode.gif]: /images/20220618/d2120ad5b4ff43e886b9b21706a2ebf2.png
[Link 1]: http://www.cnblogs.com/xybaby/p/6323358.html
[Link 2]: https://en.wikipedia.org/wiki/Coroutine#Implementations_for_Python