Глубина рекурсии обхода дерева 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

Реальная проблема не в глубине рекурсии вашего алгоритма, которая должна быть около 10 для значения, такого как 300, а в том, что вы сравниваете числа с is. Ключевое слово is проверяет идентичность объекта, а == проверяет равенство:

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

Из-за этого ваше условие if, которое должно прекратить рекурсию, никогда не будет истинным, и функция будет продолжать рекурсивно, даже если b и e равны.

Если вы измените if, эта проблема должна исчезнуть:

if b == e:
   ...

Для небольших чисел проблема может не возникать, поскольку Python "кэширует" и повторно использует объекты для целых чисел до определенного размера.

Answer 2

Как правило, способ преобразования из рекурсии в итеративный состоит в том, чтобы поддерживать стек (или очередь) вручную.

Что-то вроде:

 while stack is not empty:
     item = pop from stack

     do processing (such as adding onto the node)

     push L and R onto the stack

Стек увеличивается в памяти, так как для каждого элемента, который вы щелкаете, вы нажимаете два.