0

I want to dissolve the recursion of the following function because some input data lead to an exceeding recursion depth error. Increasing the recursion depth is not a solution in the long-run.

def foo(x):
    for element in x.elements:
        element.depth = x.depth + 1
        self.foo(element)

List flattening is not applicable since the original list structure needs to be preserved.

This solution uses a generator, containing a recursion though. Does the fact that it is a generator make a difference?

Finally, there is the stack approach. Here, I am not sure if this is 100% applicable since the interdependence of the to-be-assigned values.

What would be an elegant (Pythonic), non-recursive solution?

Community
  • 1
  • 1
fotinsky
  • 972
  • 2
  • 10
  • 25

2 Answers2

1

You are basically implementing a DFS on your data. Your data is graph where each element is a node, and a connection between two elements is an edge.

You can easily replace recursive DFS with a stack DFS by iterating elements and pushing to stack, and keep doing so until stack is exhausted.

Be aware that there might be a small difference in the ordering of elements, but that can be solved easily as well.

The pseudo code for DFS will be:

def foo(x):
   s = new stack
   s.push(x)
   while not s.empty()
   e = s.pop()
     for element in e.elements:  # or elements[::-1] for reversed order
          element.depth = e.depth + 1
          s.push(element)
          # if data structure is not a tree, add visited set.
Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
1
def foo(x):
    stack = [(x,0)]
    while stack:
        node,depth = stack.pop(0)
        node.depth = depth
        stack.extend([(ele,depth+1) for ele in node.elements if ele])

I think at least... based on your description

Joran Beasley
  • 110,522
  • 12
  • 160
  • 179