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)

当N大约为300时，这段代码会出现最大递归深度超出限制的错误。有没有办法用迭代的方式来创建这个树，而不是用递归的方式呢？

Answer 1

一般来说，把递归转换成循环的方法，就是手动维护一个栈（或队列）。

可以这样理解：

 while stack is not empty:
     item = pop from stack

     do processing (such as adding onto the node)

     push L and R onto the stack

在这个过程中，栈的内存会增加，因为每次你从栈里取出一个东西时，你又会放入两个东西。

Answer 2

真正的问题不是你算法的递归深度，对于像300这样的数值，递归深度应该大约是10，而是你在用is来比较数字。is这个关键词是用来检查对象的身份，也就是说它判断的是两个对象是不是同一个东西，而==则是用来检查两个对象的值是否相等：

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

因此，你的if条件本来是用来结束递归的，但它永远不会为真，所以函数会一直递归下去，即使b和e的值是相等的。

如果你修改一下if的写法，这个问题就应该能解决：

if b == e:
   ...

对于小数字来说，这个问题可能不会出现，因为Python会对一定范围内的整数进行“缓存”和重用。