Python中的递归生成器

Question

我写了一个函数，用于返回一个生成器，其中包含每个唯一组合的子字符串，其长度为给定长度且包含来自主字符串的n个以上元素。

举个例子：

如果我有'abcdefghi'，探针长度为2，阈值为每个列表4个元素，我希望得到：

['ab', 'cd', 'ef', 'gh']
['ab', 'de', 'fg', 'hi']
['bc', 'de', 'fg', 'hi']

我第一次尝试解决这个问题时，返回了一个列表的列表。结果导致计算机的内存溢出。作为一种粗糙的备选方案，我创建了一个类似的生成器。问题是我创建了一个调用自身的嵌套生成器。当我运行这个函数时，它似乎只是在内部循环中循环而没有实际调用自身。我以为生成器会一直向下递归到达yield语句所在的位置。有什么线索吗？

def get_next_probe(self, current_probe_list, probes, unit_length):
    if isinstance(current_probe_list, list):
        last_probe=current_probe_list[-1]
        available_probes = [candidate for candidate in probes if candidate.start>last_probe.end]
    else:
        available_probes = [candidate for candidate in probes if candidate.start<unit_length]

    if available_probes:

        max_position=min([probe.end for probe in available_probes])
        available_probes2=[probe for probe in available_probes if max_position+1>probe.start]

        for new_last_probe in available_probes2:
            new_list=list(current_probe_list)
            new_list.append(new_last_probe)
            self.get_next_probe(new_list, probes, unit_length)

    else:
        if len(current_probe_list)>=self.num_units:
            yield current_probe_list

如果将yield更改为print，则可以正常工作！我将不胜感激，如果能得到任何帮助。我意识到这不是这种搜索问题的最佳实现方式，似乎从get_next_probe的最后一次调用返回找到的位置列表，并过滤不重叠new_last_probe.end的元素，会更加高效...但这对我来说更容易编写。仍然欢迎任何算法输入。

谢谢！

- user1348971

---

你似乎没有使用递归调用的结果。我期望看到一个内部循环，遍历外部列表的子列表，将递归调用的结果连接起来形成所需的结果。 - Lawrence D'Oliveiro

你在第一行和ab处缺少引号。 - Stuart Siegler

Answer 1

我原本认为，生成器会一直跟随递归向下走，直到遇到yield语句

它会很好地递归，但要让yield的值传播回外部，你需要显式地做出操作 - 就像如果是一个return，你需要显式地return每个递归的结果一样。所以，不是：

 self.get_next_probe(new_list, probes, unit_length)

您可以这样做：

 for val in self.get_next_probe(new_list, probes, unit_length):
     yield val

如果您使用的是Python 3.3或更高版本，也可以这样做：

yield from self.get_next_probe(new_list, probes, unit_length)

- lvc

---

从 Python 3.2 开始，你也可以这样写：yield from self.get_next_prob(...)。 - Danica

@Dougal，yield from在3.2中不存在，但一旦3.3发布，它将会出现。 - lvc

好观点@Ivc...你会认为在这么说之前我可以检查一下，因为我现在大部分的代码都是用3.2编写的。 :) - Danica