Python 生成器可以递归吗？

Can generators be recursive?

提问by Aguy

I naively tried to create a recursive generator. Didn't work. This is what I did:

我天真地尝试创建一个递归生成器。没用。这就是我所做的：

def recursive_generator(lis):
    yield lis[0]
    recursive_generator(lis[1:])

for k in recursive_generator([6,3,9,1]):
    print(k)

All I got was the first item 6.

我得到的只是第一项6。

Is there a way to make such code work? Essentially transferring the yieldcommand to the level above in a recursion scheme?

有没有办法让这样的代码工作？本质yield上在递归方案中将命令转移到上面的级别？

回答by Alec

Try this:

尝试这个：

def recursive_generator(lis):
    yield lis[0]
    yield from recursive_generator(lis[1:])

for k in recursive_generator([6,3,9,1]):
    print(k)

I should point out this doesn't work because of a bug in your function. It should probably include a check that lisisn't empty, as shown below:

我应该指出这不起作用，因为您的函数中存在错误。它可能应该包括一个lis非空的支票，如下所示：

def recursive_generator(lis):
    if lis:
        yield lis[0]
        yield from recursive_generator(lis[1:])

In case you are on Python 2.7 and don't have yield from, check this question out.

如果您使用的是 Python 2.7 而没有yield from，请查看此问题。

回答by Daniele Barresi

Why your code didn't do the job

为什么你的代码没有完成这项工作

In your code, the generator function:

在您的代码中，生成器函数：

1. returns(yields) the first value of the list
2. then it creates a new iterator objectcalling the same generator function, passing a slice of the list to it
3. and then stops

1. 返回（产生）列表的第一个值
2. 然后它创建一个新的迭代器对象，调用相同的生成器函数，将列表的一部分传递给它
3. 然后停止

The second instance of the iterator, the one recursively created, is never being iterated over. That's why you only got the first item of the list.

迭代器的第二个实例，即递归创建的实例，永远不会被迭代。这就是为什么你只得到了列表的第一项。

A generator function is useful to automatically create an iterator object (an object that implements the iterator protocol), but then you need to iterate over it: either manuallycalling the next()method on the object or by means of a loop statement that will automatically use the iterator protocol.

生成器函数可用于自动创建迭代器对象（实现迭代器协议的对象），但随后您需要对其进行迭代：手动调用next()对象上的方法或通过循环语句自动使用迭代器协议。

So, can we recursively call a generator?

那么，我们可以递归调用生成器吗？

The answer is yes. Now back to your code, if you reallywant to do this with a generator function, I guess you could try:

答案是肯定的。现在回到你的代码，如果你真的想用生成器函数来做到这一点，我想你可以尝试：

def recursive_generator(some_list):
    """
    Return some_list items, one at a time, recursively iterating over a slice of it... 
    """
    if len(some_list)>1:
    # some_list has more than one item, so iterate over it
        for i in recursive_generator(some_list[1:]):
            # recursively call this generator function to iterate over a slice of some_list.
            # return one item from the list.
            yield i
        else:
            # the iterator returned StopIteration, so the for loop is done.
            # to finish, return the only value not included in the slice we just iterated on.
            yield some_list[0]
    else:
        # some_list has only one item, no need to iterate on it.
        # just return the item.
        yield some_list[0]

some_list = [6,3,9,1]
for k in recursive_generator(some_list):
    print(k)

Note:the items are returned in reversed order, so you might want to use some_list.reverse()before calling the generator the first time.

注意：项目以相反的顺序返回，因此您可能希望some_list.reverse()在第一次调用生成器之前使用。

The important thing to note in this example is: the generator function recursively calls itself in a forloop, which sees an iterator and automatically uses the iteration protocol on it, so it actually gets values from it.

在这个例子中需要注意的重要一点是：生成器函数在for循环中递归调用自己，它看到一个迭代器并自动在它上面使用迭代协议，所以它实际上从中获取值。

This works, but I think this is really not useful. We are using a generator function to iterate over a list and just get the items out, one at a time, but... a list is an iterable itself, so no need for generators! Of course I get it, this is just an example, maybe there are useful applications of this idea.

这有效，但我认为这真的没有用。我们正在使用一个生成器函数来迭代一个列表，一次一个地取出项目，但是……一个列表本身就是一个可迭代的，所以不需要生成器！我当然明白，这只是一个例子，也许这个想法有一些有用的应用。

Another example

另一个例子

Let's recycle the previous example (for lazyness). Lets say we need to print the items in a list, adding to every item the count of previous items (just a random example, not necessarily useful).

让我们再循环前面的例子（为了懒惰）。假设我们需要打印列表中的项目，向每个项目添加先前项目的计数（只是一个随机示例，不一定有用）。

The code would be:

代码将是：

def recursive_generator(some_list):
    """
    Return some_list items, one at a time, recursively iterating over a slice of it...
    and adding to every item the count of previous items in the list
    """
    if len(some_list)>1:
    # some_list has more than one item, so iterate over it
        for i in recursive_generator(some_list[1:]):
            # recursively call this generator function to iterate over a slice of some_list.
            # return one item from the list, but add 1 first. 
            # Every recursive iteration will add 1, so we basically add the count of iterations.
            yield i + 1
        else:
            # the iterator returned StopIteration, so the for loop is done.
            # to finish, return the only value not included in the slice we just iterated on.
            yield some_list[0]
    else:
        # some_list has only one item, no need to iterate on it.
        # just return the item.
        yield some_list[0]

some_list = [6,3,9,1]
for k in recursive_generator(some_list):
    print(k)

Now, as you can see, the generator function is actually doing something before returning list items AND the use of recursion starts to make sense. Still, just a stupid example, but you get the idea.

现在，如您所见，生成器函数实际上是在返回列表项之前执行某些操作，并且递归的使用开始变得有意义。尽管如此，这只是一个愚蠢的例子，但你明白了。

Note:off course, in this stupid example the list is expected to contain only numbers. If you really want to go try and break it, just put in a string in some_listand have fun. Again, this is only an example, not productioncode!

注意：当然，在这个愚蠢的例子中，列表应该只包含数字。如果你真的想尝试打破它，只需在some_list 中放入一个字符串并玩得开心。同样，这只是一个例子，不是生产代码！

回答by Terry Jan Reedy

Recursive generators are useful for traversing non-linear structures. For example, let a binary tree be either None or a tuple of value, left tree, right tree. A recursive generator is the easiest way to visit all nodes. Example:

递归生成器可用于遍历非线性结构。例如，让二叉树为 None 或值元组，左树，右树。递归生成器是访问所有节点的最简单方法。例子：

tree = (0, (1, None, (2, (3, None, None), (4, (5, None, None), None))),
        (6, None, (7, (8, (9, None, None), None), None)))

def visit(tree):  # 
    if tree is not None:
        try:
            value, left, right = tree
        except ValueError:  # wrong number to unpack
            print("Bad tree:", tree)
        else:  # The following is one of 3 possible orders.
            yield from visit(left)
            yield value  # Put this first or last for different orders.
            yield from visit(right)

print(list(visit(tree)))

# prints nodes in the correct order for 'yield value' in the middle.
# [1, 3, 2, 5, 4, 0, 6, 9, 8, 7]

Edit: replace if treewith if tree is not Noneto catch other false values as errors.

编辑：替换if tree为if tree is not None以捕获其他错误值作为错误。

Edit 2:about putting the recursive calls in the try: clause (comment by @jpmc26).

编辑 2：关于将递归调用放在 try: 子句中（@jpmc26 的评论）。

For bad nodes, the code above just logs the ValueError and continues. If, for instance, (9,None,None)is replaced by (9,None), the output is

对于坏节点，上面的代码只记录 ValueError 并继续。例如，如果(9,None,None)被替换为(9,None)，则输出为

Bad tree: (9, None)
[1, 3, 2, 5, 4, 0, 6, 8, 7]

More typical would be to reraise after logging, making the output be

更典型的是在记录后重新加注，使输出成为

Bad tree: (9, None)
Traceback (most recent call last):
  File "F:\Python\a\tem4.py", line 16, in <module>
    print(list(visit(tree)))
  File "F:\Python\a\tem4.py", line 14, in visit
    yield from visit(right)
  File "F:\Python\a\tem4.py", line 14, in visit
    yield from visit(right)
  File "F:\Python\a\tem4.py", line 12, in visit
    yield from visit(left)
  File "F:\Python\a\tem4.py", line 12, in visit
    yield from visit(left)
  File "F:\Python\a\tem4.py", line 7, in visit
    value, left, right = tree
ValueError: not enough values to unpack (expected 3, got 2)

The traceback gives the path from the root to the bad node. One could wrap the original visit(tree)call to reduce the traceback to the path: (root, right, right, left, left).

回溯给出了从根到坏节点的路径。可以包装原始visit(tree)调用以减少对路径的回溯：（根，右，右，左，左）。

If the recursive calls are included in the try: clause, the error is recaught, relogged, and reraised at each level of the tree.

如果递归调用包含在 try: 子句中，则会在树的每个级别重新捕获、重新记录和重新引发错误。

Bad tree: (9, None)
Bad tree: (8, (9, None), None)
Bad tree: (7, (8, (9, None), None), None)
Bad tree: (6, None, (7, (8, (9, None), None), None))
Bad tree: (0, (1, None, (2, (3, None, None), (4, (5, None, None), None))), (6, None, (7, (8, (9, None), None), None)))
Traceback (most recent call last):
...  # same as before

The multiple logging reports are likely more noise than help. If one wants the path to the bad node, it might be easiest to wrap each recursive call in its own try: clause and raise a new ValueError at each level, with the contructed path so far.

多个日志报告可能更多是噪音而不是帮助。如果想要找到坏节点的路径，最简单的方法是将每个递归调用包装在自己的 try: 子句中，并在每个级别引发一个新的 ValueError，到目前为止已构建路径。

Conclusion: if one is not using an exception for flow control (as may be done with IndexError, for instance) the presence and placements of try: statements depends on the error reporting one wants.

结论：如果不使用异常进行流量控制（例如，可以使用 IndexError 完成），try: 语句的存在和位置取决于人们想要的错误报告。

回答by Levon

Up to Python 3.4, a generator function used to have to raise StopIterationexception when it is done. For the recursive case other exceptions (e.g. IndexError) are raised earlier than StopIteration, therefore we add it manually.

在 Python 3.4 之前，生成器函数过去必须在StopIteration完成时引发异常。对于递归情况，其他异常（例如IndexError）在 之前引发StopIteration，因此我们手动添加它。

def recursive_generator(lis):
    if not lis: raise StopIteration
    yield lis[0]
    yield from recursive_generator(lis[1:])

for k in recursive_generator([6, 3, 9, 1]):
    print(k)

---

---

def recursive_generator(lis):
    if not lis: raise StopIteration
    yield lis.pop(0)
    yield from recursive_generator(lis)

for k in recursive_generator([6, 3, 9, 1]):
    print(k)

Note that forloop will catch StopIterationexception. More about this here

请注意，for循环将捕获StopIteration异常。更多关于这里

回答by Elliot Cameron

Yes you can have recursive generators. However, they suffer from the same recursion depth limit as other recursive functions.

是的，您可以使用递归生成器。然而，它们受到与其他递归函数相同的递归深度限制。

def recurse(x):
  yield x
  yield from recurse(x)

for (i, x) in enumerate(recurse(5)):
  print(i, x)

This loop gets to about 3000 (for me) before crashing.

这个循环在崩溃之前达到大约 3000（对我来说）。

However, with some trickery, you can create a function that feeds a generator to itself. This allows you to write generators like they are recursive but are not: https://gist.github.com/3noch/7969f416d403ba3a54a788b113c204ce

但是，通过一些技巧，您可以创建一个函数，将生成器提供给自身。这允许您编写像递归但不是递归的生成器：https: //gist.github.com/3noch/7969f416d403ba3a54a788b113c204ce

回答by Y Nehc

The reason your recursive call only executes once is that you are essentially creating nested generators. That is, you are creating a new generator inside a generator each time you call the function recursive_generator recursively.

您的递归调用只执行一次的原因是您实际上是在创建嵌套生成器。也就是说，每次递归调用函数 recursive_generator 时，都会在生成器中创建一个新生成器。

Try the following and you will see.

尝试以下操作，您将看到。

def recursive_generator(lis):
    yield lis[0]
    yield recursive_generator(lis[1:])

for k in recursive_generator([6,3,9,1]):
    print(type(k))

One simple solution, like others mention, is to use yield from.

就像其他人提到的那样，一种简单的解决方案是使用yield from.