Databases
StackOverflow2013
Postsdbo
POPython recursive function exceeds recursion limit. How can I convert it to iteration
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POPython recursive function exceeds recursion limit. How can I convert it to iteration
    primarykey
    data
    text
    <p>I have created a function that reads lists of ID pairs (i.e. [("A","B"),("B","C"),("C","D"),...] and sequences the ID's from start to finish including any branches.</p> <p>Each list of ordered ID's is held in a class called an Alignment and this function uses recursion to handle branches by creating a new alignment starting at the ID at which the branch splits from the main list.</p> <p>I have found that with certain inputs it is possible to reach the maximum recursion limit set by Python. I know I could just increase this limit using sys.setrecursionlimit(), but as I do not know how many combinations of branches are possible, I'd like to avoid this tactic.</p> <p>I have been reading several articles about converting recursive functions to iterative functions, but I have not been able to determine the best way to handle this particular function because the recursion takes place in the middle of the function and can be exponential.</p> <p>Could any of you offer any suggestions?</p> <p>Thanks, Brian</p> <p>Code is posted below:</p> <pre><code>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 &lt; 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 </code></pre> <p>EDIT: I should point out that the provided IDs are just a small sample I used for testing this algorithm. In actuality, the sequences of IDs may be several thousand long with many branches and branches off of branches.</p> <p>RESOLUTION: Thanks to Andrew Cooke. The new method seems to be much simpler and much easier on the call stack. I did make some minor adjustments to his code to better suit my purposes. I have included the completed solution below:</p> <pre><code>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")]) </code></pre> <p>SUMMARY OF CHANGES: swapped links and have_successors to create list from start to end added <code>if line in known: known.remove(line)</code> to expand in order to retain only the complete series changed line variable from string to list in order to handle multiple characters in a single ID.</p> <p>UPDATE: So I just discovered the reason I was having an issue with all this in the first place is do to circular references in the list of IDs I was provided. Now that the circular reference is fixed, either method works as expected. - Thanks again for all your help.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USBrian
    1. USBrian
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POPython recursive function exceeds recursion limit. How can I convert it to iteration
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POPython recursive function exceeds recursion limit. How can I convert it to iteration
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POPython recursive function exceeds recursion limit. How can I convert it to iteration
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI think you mean offshoots.
      singulars
      1. POPython recursive function exceeds recursion limit. How can I convert it to iteration
      1. This table or related slice is empty.
    2. COIs this your actual code? It throws IndexError at `i = len(alignments)` ... `buildAlignments(alignments[i]` before it even starts recursing.
      singulars
      1. POPython recursive function exceeds recursion limit. How can I convert it to iteration
      1. USBaffe Boyois
    3. CO@Erin - thanks for pointing that out. I have changed off-chutes to branches as it is a better description.
      singulars
      1. POPython recursive function exceeds recursion limit. How can I convert it to iteration
      1. USBrian
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload