生成器可以递归吗？

Question

我天真地尝试创建一个递归生成器.没工作.这就是我做的:

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

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

我得到的只是第一项6.

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

Answer 1

试试这个:

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

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

我应该指出,由于你的功能有一个错误,这不起作用.它可能应该包含一个lis非空的检查,如下所示:

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

如果您使用的是Python 2.7并且没有yield from,请查看此问题.

Answer 2

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

在您的代码中,生成器函数:

1. 返回(yield)列表的第一个值
2. 然后它创建一个新的迭代器对象,调用相同的生成器函数,将列表的一部分传递给它
3. 然后停下来

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

生成器函数对于自动创建迭代器对象(实现迭代器协议的对象)非常有用,但是您需要迭代它:手动调用next()对象上的方法或通过循环语句自动使用迭代器协议.

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

答案是肯定的.现在回到你的代码,如果你真的想用生成器函数做这个,我想你可以尝试:

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)

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

在这个例子中需要注意的重要事项是:生成器函数在for循环中递归调用自身,它看到迭代器并自动使用迭代协议,因此它实际上从中获取值.

这有效,但我认为这实际上没用.我们正在使用生成器函数迭代列表并且只是一次一个地获取项目,但是...列表本身是可迭代的,因此不需要生成器!当然我明白了,这只是一个例子,也许这个想法有用.

另一个例子

让我们回收前面的例子(对于懒惰).让我们说我们需要在列表中打印项目,向每个项目添加先前项目的计数(只是一个随机的例子,不一定有用).

代码是:

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)

现在,正如您所看到的,生成器函数在返回列表项之前实际上正在执行某些操作,并且递归的使用开始有意义.不过,这只是一个愚蠢的例子,但你明白了.

注意:当然,在这个愚蠢的例子中,列表应该只包含数字.如果你真的想尝试打破它,只需在some_list中输入一个字符串并享受乐趣.同样,这只是一个例子,而不是生产代码!

Answer 3

递归生成器对于遍历非线性结构非常有用.例如,让二叉树为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]

编辑:更换if tree与if tree is not None追赶其他错误值的误差.