使用产量的递归

有什么方法可以混合递归和 yield语句吗？例如，无限数生成器(使用递归)类似于:

def infinity(start):
yield start
# recursion here ...


>>> it = infinity(1)
>>> next(it)
1
>>> next(it)
2

我试过:

def infinity(start):
yield start
infinity(start + 1)

还有

def infinity(start):
yield start
yield infinity(start + 1)

但是他们都没有按我说的做，第一个在生成 start之后就停止了，第二个生成 start之后就停止了，然后是发电机，然后就停止了。

注意: 请注意，我知道您可以使用 while 循环来完成此操作:

def infinity(start):
while True:
yield start
start += 1

我只想知道这是否可以递归完成。

47384 次浏览
小开
最佳答案

Yes, you can do this:

def infinity(start):
yield start
for x in infinity(start + 1):
yield x

This will error out once the maximum recursion depth is reached, though.

Starting from Python 3.3, you'll be able to use

def infinity(start):
yield start
yield from infinity(start + 1)

If you just call your generator function recursively without looping over it or yield from-ing it, all you do is build a new generator, without actually running the function body or yielding anything.

See PEP 380 for further details.

小开

In some cases it might be preferable to use a stack instead of recursion for generators. It should be possible to rewrite a recursive method using a stack and a while loop.

Here's an example of a recursive method which uses a callback and can be rewritten using stack logic:

def traverse_tree(callback):
# Get the root node from somewhere.
root = get_root_node()
def recurse(node):
callback(node)
for child in node.get('children', []):
recurse(child)
recurse(root)

The above method traverses a node tree where each node has a children array which may contain child nodes. As each node is encountered, the callback is issued and the current node is passed to it.

The method could be used this way, printing out some property on each node.

def callback(node):
print(node['id'])
traverse_tree(callback)

Use a stack instead and write the traversal method as a generator

# A stack-based alternative to the traverse_tree method above.
def iternodes():
stack = [get_root_node()]
while stack:
node = stack.pop()
yield node
for child in reversed(node.get('children', [])):
stack.append(child)

(Note that if you want the same traversal order as originally, you need to reverse the order of children because the first child appended to the stack will be the last one popped.)

Now you can get the same behavior as traverse_tree above, but with a generator:

for node in iternodes():
print(node['id'])

This isn't a one-size-fits-all solution but for some generators you might get a nice result substituting stack processing for recursion.

小开 
def lprint(a):
if isinstance(a, list):
for i in a:
yield from lprint(i)
else:
yield a


b = [[1, [2, 3], 4], [5, 6, [7, 8, [9]]]]
for i in lprint(b):
print(i)

提交答案