Python递归函数超出了递归限制。如何将其转换为迭代

Question

我创建了一个读取ID对列表的函数(即[(“A”，“B”)，(“B”，“C”)，(“C”，“D”)，...]和序列) ID从头到尾，包括所有分支。

每个有序ID的列表都保存在一个称为Alignment的类中，此函数使用递归来处理分支，方法是从该ID从主列表中拆分出的ID开始创建一个新的对齐方式。

我发现使用某些输入可以达到Python设置的最大递归限制。我知道我可以使用sys.setrecursionlimit()来增加此限制，但是由于我不知道可能有多少分支组合，因此我想避免这种策略。

我已经阅读了几篇有关将递归函数转换为迭代函数的文章，但是由于递归发生在函数的中间并且可能是指数式的，因此我无法确定处理此特定函数的最佳方法。

你们中的任何人都可以提供任何建议吗？

谢谢，布莱恩

代码如下:

def buildAlignments(alignment, alignmentList, endIDs):
    while alignment.start in endIDs:

        #If endID only has one preceding ID: add preceding ID to alignment
        if len(endIDs[alignment.start]) == 1:
            alignment.add(endIDs[alignment.start][0])

        else:

            #List to hold all branches that end at spanEnd
            branches = []

            for each in endIDs[alignment.start]:

                #New alignment for each branch
                al = Alignment(each)

                #Recursively process each new alignment
                buildAlignments(al, branches, endIDs)

                branches.append(al)
            count = len(branches)
            i = 0
            index = 0

            #Loop through branches by length
            for branch in branches:
                if i < count - 1:

                    #Create copy of original alignment and add branch to alignment
                    al = Alignment(alignment)
                    al += branch #branches[index]
                    alignmentList.append(al)
                    i += 1

                #Add single branch to existing original alignment
                else: alignment += branch #branches[index]
                index += 1

def main():
    IDs = [("L", "G"), ("A", "B"), ("B", "I"), ("B", "H"), ("B", "C"), ("F", "G"), ("D", "E"), ("D", "J"), ("E", "L"), ("C", "D"), ("E", "F"), ("J", "K")]

    #Gather all startIDs with corresponding endIDs and vice versa
    startIDs = {}
    endIDs = {}
    for pair in IDs:
        if not pair[0] in startIDs: startIDs[pair[0]] = []
        startIDs[pair[0]].append(pair[1])
        if not pair[1] in endIDs: endIDs[pair[1]] = []
        endIDs[pair[1]].append(pair[0])

    #Create Alignment objects from any endID that does not start another pair (i.e. final ID in sequence)
    alignments = [Alignment(end) for end in endIDs if not end in startIDs]

    #Build build sequences in each original Alignment
    i = len(alignments)
    while i:
        buildAlignments(alignments[i-1], alignments, endIDs)
        i -= 1

编辑:我应该指出，提供的ID只是我用于测试该算法的一个小样本。实际上，ID的序列可能有数千个长度，并且有许多分支并且分支不在分支中。

解决方法:感谢安德鲁·库克。在调用堆栈上，新方法似乎更简单，更容易。我确实对他的代码做了一些小的调整，以更好地满足我的目的。我在下面包括了完整的解决方案:

from collections import defaultdict

def expand(line, have_successors, known):
    #print line
    known.append(line)
    for child in have_successors[line[-1]]:
        newline = line + [child]
        if line in known: known.remove(line)
        yield expand(newline, have_successors, known)

def trampoline(generator):
    stack = [generator]
    while stack:
        try:
            generator = stack.pop()
            child = next(generator)
            stack.append(generator)
            stack.append(child)
        except StopIteration:
            pass

def main(pairs):
    have_successors = defaultdict(lambda: set())
    links = set()
    for (start, end) in pairs:
        links.add(end)
        have_successors[start].add(end)
    known = []
    for node in set(have_successors.keys()):
        if node not in links:
            trampoline(expand([node], have_successors, known))
    for line in known:
        print line

if __name__ == '__main__':
    main([("L", "G"), ("A", "B"), ("B", "I"), ("B", "H"), ("B", "C"), ("F", "G"), ("D", "E"), ("D", "J"), ("E", "L"), ("C", "D"), ("E", "F"), ("J", "K")])

变更摘要:
交换链接和have_successors从头到尾创建列表
添加了 if line in known: known.remove(line)进行扩展以仅保留完整系列
将行变量从字符串更改为列表，以便在单个ID中处理多个字符。

更新:所以我才发现我最初遇到的所有问题的原因是对我提供的ID列表中的循环引用。现在，循环引用已固定，无论哪种方法都能按预期工作。 - 再次感谢你的帮助。

Answer 1

您的代码是困惑的。我不知道应该怎么做。如果您更加谨慎(更整洁，更清晰)，那么您可能还会发现重构更容易。

无论如何，这可能会做您想要的事情:

from collections import defaultdict

def expand(line, links, known):
    print 'expand'
    known.append(line)
    for child in links[line[-1]]:
        newline = line + child
        yield expand(newline, links, known)

def trampoline(generator):
    stack = [generator]
    while stack:
        try:
            generator = stack.pop()
            print 'next'
            child = next(generator)
            stack.append(generator)
            stack.append(child)
        except StopIteration:
            pass

def main(pairs):
    have_successors = set()
    links = defaultdict(lambda: set())
    for (start, end) in pairs:
        have_successors.add(start)
        links[end].add(start)
    known = []
    for node in set(links.keys()):
        if node not in have_successors:
            trampoline(expand(node, links, known))
    for line in known:
        print line

if __name__ == '__main__':
    main([("L", "G"), ("A", "B"), ("B", "I"), ("B", "H"), ("B", "C"), ("F", "G"), ("D", "E"), ("D", "J"), ("E", "L"), ("C", "D"), ("E", "F"), ("J", "K")])

我使用python2.7-对于早期版本，您可能需要将 next(foo)替换为 foo.__next__()或类似名称。

编写更清洁的代码

首先，我也是一名自学成才的程序员，最初是一名学者(天文学家)，所以您对此表示同情。如果继续前进，您可以 catch 并通过许多“教书”的程序员。它并不像您想象的那么难...

其次，使用像defaultdict这样的“技巧”(只是经验/实践问题)和“整理”之间是有区别的。我不希望您了解defaultdict-这将随时间而来。

但是您现在应该能够做的是编写干净，简单的代码:

我认为您有关于早期版本代码的注释。一个提到“最大长度”，但我看不到任何长度的计算。因此，要么评论已过时(在这种情况下，为什么会出现在评论中)，要么需要使其更清晰(为什么这些东西的长度最大？)。通常，您应该尽量少评论，因为否则它确实会过时。但是同时您应该在不清楚代码背后的“想法”的地方使用注释。该代码应能说明一切，所以不要说“我在这里加两个数字”，而要说“这里的片段必须是最大长度，因为...”，如果有一些“隐藏”逻辑。

请小心使用的图片。由于某种原因，您的代码以已知的终端开头。所以您要从头开始构建所有东西。为什么？这是解决问题的一种奇怪方法。从起点开始而不是终点开始更清晰吗？然后使用“startID”来增长它们？这样，您就可以“向前走”。这看起来似乎有点小事，但它会使阅读代码变得困惑。

使用正确的工具完成工作。您没有使用startID，那么为什么要构建 map ？您需要的只是一套。也许您不了解集合，在这种情况下可以(但现在就知道了!:o)。但是否则，这也令人困惑-读取您的代码的某人希望您做某事是有原因的。因此，当您做的事超出必要时，他们会想为什么。

避免在不需要时计算事物。您有i，index和count。他们都需要吗？这类计数器是产生错误的最简单方法，因为它们可能只有很小的逻辑错误。他们使代码不清楚。 if i < count - 1:真的在说“这是最后一个分支”吗？如果是这样，那么编写if branch == branches [-1]:会更好，因为这很清楚您在想什么。

与循环遍历main中的对齐方式类似。使用i只会使事情复杂化。您正在处理每个对齐方式，所以只需说for each alignment in alignments即可。如果由于对齐方式更改而导致错误，请创建不变的副本:for each alignment in list(alignments)。

避免特殊情况(如果不需要)。在buildAlignment中，对于特殊情况，您一开始就可以进行测试。但是真的需要吗？没有它，您会得到相同的结果吗？通常，当您简单地编写代码时，事实证明您不需要特殊情况。在我的代码中，我不需要测试是否存在“链接”，因为在所有这些情况下它都可以正常工作。这使您减少了代码，减少了需要担心的事情，并减少了发生错误的机会。

不仅仅是所有这些事情-您还必须 整洁和有条理的。您有很多想法，但不要尝试一个想法的一半，而是跳到另一个想法，写下来并逐一进行研究。否则，您将陷入一团乱码和您不了解的代码。起初感觉就像是在浪费时间，但是您开始看到结果是您变得越来越快，因为花费的时间更少了。

生成器上的

[我稍微修改了代码，以分离出 newline并在几个地方添加了 print。]

首先，您是否运行了代码？它在做您想要的事情吗？您能看到它与以前的事物如何联系吗？我的 expand与您的 buildAlignment相似(我希望如此)。

如果您运行它(最新版本)，则会看到:

: python2.7 recurse.py
next
expand
next
expand
next
expand
next
expand
next
expand
next
expand
next
expand
next
next
...

这可能为正在发生的事情提供线索。 “技巧”是yield语句-python编译器会看到这一点，而不是生成普通函数，而是生成一个生成器。

发电机是很奇怪的事情。它基本上是您的函数(在本例中为 expand)，它是“捆绑”的，因此可以分阶段运行。运行是通过 next()完成的，并且每次到达 yield时，函数都会再次停止。

因此 trampoline传递了这个奇怪的捆绑包。它调用 next()。那就是启动该功能的“魔术”功能。因此，当调用 next时，该函数开始运行，直到到达 yield为止，在此它返回新的包。然后 trampoline()命令保存旧的捆绑包并开始处理新的捆绑包，在其上调用 next()，将其启动...等等

当生成器“无所事事”时，它将引发 StopIteration。因此，当我们达到表达式无法再增长的程度时，我们会在 trampoline()中看到该异常。在这一点上，我们返回到最后一个“旧”捆绑包(存储在 stack中)，并在其上再次调用 next()。该捆绑软件从其所在位置重新开始(紧接在 yield之后)并继续，可能在 while中进行了另一个循环，直到再次击中 yield(或用完并引发 StopIteration)为止。

所以最后，代码的作用与 yield不存在的相同!唯一的区别是我们继续制作这些捆绑包，并将其退还。这似乎毫无意义。除了我们不再使用堆栈!因为返回了捆绑包，所以堆栈没有被“用完”!这就是为什么我们需要管理自己的堆栈(列表 stack)的原因-否则无法知道上一个调用是什么。

好吧，好吧，我不希望您完全理解这一点。是的，这有点疯狂。现在，您需要离开Goog​​le搜索“python generators”。并编写自己的代码进行测试。但希望这指明了方向。

哦，也是，我昨晚在想。我怀疑如果您要耗尽堆栈，实际上是因为您有循环，而不是因为链条太长了。你考虑过循环吗？ A-> B，B-> C，C-> A，...