Python递归函数超出递归限制，如何转换为迭代？

Question

我创建了一个函数，可以读取一对对的ID列表，比如说[("A","B"),("B","C"),("C","D"),...]，并且把这些ID从开始到结束按顺序排列，包括任何分支。

每一组有序的ID都保存在一个叫做Alignment的类里，这个函数使用递归来处理分支，也就是在分支从主列表分开的地方创建一个新的对齐。

我发现，有些输入会让Python达到最大递归限制。我知道可以用sys.setrecursionlimit()来增加这个限制，但因为我不知道可能有多少种分支组合，所以我想避免这样做。

我看了很多关于把递归函数转换成迭代函数的文章，但我还没找到处理这个特定函数的最佳方法，因为递归发生在函数的中间，并且可能是指数级的。

有没有人能给我一些建议呢？

谢谢，Brian

代码如下：

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的序列可能会长达几千个，并且有很多分支和分支的分支。

解决方案：感谢Andrew Cooke。新的方法似乎简单多了，对调用栈的压力也小了。我对他的代码做了一些小调整，以更好地适应我的需求。下面是完整的解决方案：

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)以扩展，保留完整的序列将line变量从字符串改为列表，以处理单个ID中的多个字符。

更新：我刚发现我最开始遇到问题的原因是因为我提供的ID列表中有循环引用。现在循环引用修复后，任一方法都能按预期工作。再次感谢大家的帮助。

数据结构递归算法优化调用栈迭代循环引用分支处理对齐算法

Python递归函数超出递归限制，如何转换为迭代？

1 个回答

撰写回答