3

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?

Community
  • 1
  • 1
knite
  • 6,033
  • 6
  • 38
  • 54

2 Answers2

6

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.

Community
  • 1
  • 1
sth
  • 222,467
  • 53
  • 283
  • 367
1

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.

Donald Miner
  • 38,889
  • 8
  • 95
  • 118
  • Yes, I wanted to do this, but I need to do my processing on the current node after (recursively) creating the L and R nodes. I'm not sure where/how to stash the current node for future processing - on a separate stack? – knite Oct 09 '11 at 17:32
  • Well there are usually better ways to implement tree traversal (though they can get complicated with pointer twiddling and stuff) instead of using a "stack". After all if you use a stack on the heap you aren't really saving much space (well apart from a constant factor because you need to save less state) – Voo Oct 11 '11 at 00:22