Рекурсивная функция Python превышает предел рекурсии. Как я могу преобразовать его в итерацию

Я создал функцию, которая считывает списки пар идентификаторов (т.е. [(" A "," B "), (" B "," C "), (" C "," D "), ...] и упорядочивает идентификаторы от начала до конца, включая любые ветви.

Каждый список упорядоченных ID хранится в классе, называемом Alignment, и эта функция использует рекурсию для обработки ветвей, создавая новое выравнивание, начиная с идентификатора, по которому ветвь отделяется от основного списка.

Я обнаружил, что с некоторыми входными данными можно достичь максимального предела рекурсии, установленного 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

РЕДАКТИРОВАТЬ: Я должен отметить, что предоставленные идентификаторы - это всего лишь небольшой образец, который я использовал для тестирования этого алгоритма. На самом деле последовательности идентификаторов могут быть длиной в несколько тысяч с множеством ответвлений и ответвлений.

РЕШЕНИЕ: Спасибо Эндрю Куку. Новый метод кажется намного проще и проще в стеке вызовов. Я внес некоторые незначительные изменения в его код, чтобы лучше соответствовать моим целям. Я включил готовое решение ниже:

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 для создания списка от начала до конца добавлен , если строка в известном: известное.remove (строка) для расширения, чтобы сохранить только полную серию изменил строковую переменную со строки на список, чтобы обрабатывать несколько символов в одном идентификаторе.

ОБНОВЛЕНИЕ: Итак, я только что обнаружил причину, по которой у меня возникла проблема со всем этим, в первую очередь, с циклическими ссылками в списке Удостоверения мне предоставили. Теперь, когда круговая ссылка исправлена, любой метод работает должным образом. - Еще раз спасибо за вашу помощь.