Python tree traversal recursion depth exceeded

Question

I have a segment tree which holds data for a range of numbers (data structure chosen here). Here's the code:

class SegmentTree:
    def __init__(self, N):
        def _init(b, e):
            if b is e:
                data = foo() # No dependency
                return Node(b, e, data, None, None)
            else:
                mid = (b + e ) / 2

                L = _init(b, mid)
                R = _init(mid + 1, e)

                data = foo() #Data depends on L and R

                return Node(b, e, data, L, R)

        self.root = _init(1, N)

This fails for N around 300 with a max recursion depth exceeded error. Is there a way to create the tree iteratively instead of recursively?

Answer 1

The real problem is not the recursion depth of your algorithm, which should be about 10 for a value like 300, but that you are comparing numbers with is. The is keyword checks for object identity, while == checks for equality:

>>> 300 == 299+1
True
>>> 300 is 299+1
False

Because of that your if condition that should terminate the recursion will never be true and the function will keep recursing, even if b and e are equal.

If you change the if this problem should go away:

if b == e:
   ...

For small numbers the problem might not occur because Python "caches" and reuses the objects for ints up to a certain size.

Answer 2

In general, the way you convert from recursion to iterative, is to maintain the stack (or queue) manually.

Something like:

 while stack is not empty:
     item = pop from stack

     do processing (such as adding onto the node)

     push L and R onto the stack

The stack does grow in memory, since for each item you are popping, you are pushing two.