首页 > 代码库 > 无限“递归”的python程序

无限“递归”的python程序

2024-09-02 12:29:53   216人阅读

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

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

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

def a():
    b()
def b():
    a()
 
if __name__ == ‘__main__‘:
    a()
　　很快 就会抛出一个异常：RuntimeError: maximum recursion depth exceeded
　　会什么报这个异常，很简单，我们都知道子程序调用（call）需要压栈出栈，如果无限递归调用，那么就一直压栈，没有出栈，内存消耗也越来愈多。python比较高级，直接抛出这个异常，结束程序运行。
 
　　前面的文章提到协程（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，实现这个“无限递归”函数比较容易的。

 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()

 

 　　接下来用generator来模拟这个实现
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")

 

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

 

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()

This‘s Ok！

 
references：
http://www.cnblogs.com/xybaby/p/6323358.html
https://en.wikipedia.org/wiki/Coroutine#Implementations_for_Python
https://segmentfault.com/q/1010000003059446
 

无限“递归”的python程序


联系
我们