Python树遍历递归深度超出

Question

我有一个段树,它包含一系列数字的数据(这里选择的数据结构).这是代码:

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)

对于大约300的N,超过最大递归深度超出错误时,这会失败.有没有办法迭代地而不是递归地创建树？

Answer 1

真正的问题不是你的算法的递归深度,对于像300这样的值应该是大约10,但是你要比较数字is.该is关键字检查对象的身份,而==检查的平等:

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

因此,你if应该终止递归的条件永远不会成立,并且函数将保持递归,即使b并且e相等.

如果你改变if这个问题应该消失:

if b == e:
   ...

对于小数字,问题可能不会发生,因为Python "缓存"并重新使用对象以达到一定大小的整数.