Почему дерево по отступам в Python падает с RecursionError и как это исправить

Разбираем коварный баг при построении дерева по отступам в Python: общий список children на уровне класса вызывает RecursionError. Причина и решение.

Построить вложенное дерево из плана счетов кажется простой задачей — пока структура не начинает самовоспроизводиться, а стек не переполняется. Классическая ловушка в Python достаточно незаметна, чтобы пройти код‑ревью, но достаточно коварна, чтобы в продакшене привести к RecursionError. Ниже — короткое объяснение, почему это происходит при построении дерева по уровню отступов и как аккуратно это исправить.

Постановка задачи

Исходные данные — это план счетов, где иерархия определяется отступами. Каждый уровень смещён на три пробела. Нужно разобрать каждую строку, определить её глубину и вложить узел под соответствующего родителя.

Ниже усечённый класс и драйвер, иллюстрирующие подход:

class ChartItem:
    ancestor = None
    acct_no: int | None
    label: str
    raw_line: str
    kind: str | None
    subtype: str | None
    is_header_flag: bool = False
    children: list = list()  # список потомков, предполагавшийся для каждого отдельного экземпляра

    def __init__(self, line_in: str, ancestor=None, kind: str = None, subtype: str = None):
        self.raw_line = line_in
        self.ancestor = ancestor
        self.kind = kind
        self.subtype = subtype
        cleaned = line_in.strip()
        ...  # код, который вычисляет self.acct_no и self.label из cleaned

    def is_header(self) -> bool:
        return self.is_header_flag

    def nesting_level(self) -> int:
        return (len(self.raw_line) - len(self.raw_line.strip())) / 3

    def add_child(self, line_in, type_hint: str = None, detail_hint: str = None):
        if len(self.children) > 0:
            if calc_level(line_in) > self.children[-1].nesting_level():
                self.children[-1].add_child(line_in, type_hint=type_hint, detail_hint=detail_hint)
            else:
                self.children.append(ChartItem(
                    line_in,
                    ancestor=self,
                    kind=self.kind if type_hint is None else type_hint,
                    subtype=self.subtype if detail_hint is None else detail_hint
                ))
        else:
            self.children.append(ChartItem(
                line_in,
                ancestor=self,
                kind=self.kind if type_hint is None else type_hint,
                subtype=self.subtype if detail_hint is None else detail_hint
            ))
        return

if __name__ == "__main__":
    root_nodes: list[ChartItem] = list()
    for (row_text, type_hint, subtype_hint) in supply_rows():
        lvl = (len(row_text) - len(row_text.lstrip())) / 3
        if lvl == 0:
            root_nodes.append(ChartItem(row_text, ancestor=None, kind=type_hint, subtype=subtype_hint))
        else:
            if type_hint is not None:
                root_nodes[-1].add_child(row_text, type_hint=type_hint, detail_hint=subtype_hint)
            else:
                root_nodes[-1].add_child(row_text)

Почему всё рушится

Рекурсия появляется в ветке, которая делегирует обработку последнему потомку, если входящая строка глубже уровня вложенности этого потомка. На первый взгляд логика соответствует задумке построения дерева. Проблема в том, что список, предназначенный для хранения детей узла, объявлен на уровне класса, а не экземпляра. В Python изменяемые атрибуты, заданные у класса, общие для всех экземпляров. То есть каждый ChartItem ссылается на один и тот же список children.

Из-за общего списка условие «углубиться к последнему потомку» продолжает передавать управление узлу, который с точки зрения алгоритма не становится соседним элементом, а остаётся тем же логическим местом для всех экземпляров. Метод зовёт сам себя, стек вызовов растёт, и интерпретатор в итоге выбрасывает RecursionError. Наблюдаемое «самовложение» одного и того же узла снова и снова — закономерный итог единственного общего контейнера children для всех экземпляров.

Исправление

Сделайте контейнер children атрибутом экземпляра. Инициализируйте его в конструкторе, чтобы у каждого узла был собственный список. Остальную логику можно оставить прежней.

class ChartItem:
    ancestor = None
    acct_no: int | None
    label: str
    raw_line: str
    kind: str | None
    subtype: str | None
    is_header_flag: bool = False

    def __init__(self, line_in: str, ancestor=None, kind: str = None, subtype: str = None):
        self.raw_line = line_in
        self.ancestor = ancestor
        self.kind = kind
        self.subtype = subtype
        self.children: list[ChartItem] = []  # контейнер для потомков на уровне экземпляра
        cleaned = line_in.strip()
        ...  # код, который вычисляет self.acct_no и self.label из cleaned

    def is_header(self) -> bool:
        return self.is_header_flag

    def nesting_level(self) -> int:
        return (len(self.raw_line) - len(self.raw_line.strip())) / 3

    def add_child(self, line_in, type_hint: str = None, detail_hint: str = None):
        if len(self.children) > 0:
            if calc_level(line_in) > self.children[-1].nesting_level():
                self.children[-1].add_child(line_in, type_hint=type_hint, detail_hint=detail_hint)
            else:
                self.children.append(ChartItem(
                    line_in,
                    ancestor=self,
                    kind=self.kind if type_hint is None else type_hint,
                    subtype=self.subtype if detail_hint is None else detail_hint
                ))
        else:
            self.children.append(ChartItem(
                line_in,
                ancestor=self,
                kind=self.kind if type_hint is None else type_hint,
                subtype=self.subtype if detail_hint is None else detail_hint
            ))
        return

Когда дети больше не разделяются между экземплярами, делегирование к «последнему потомку» начинает работать как задумано: более глубокие строки уходят вниз по текущей ветке, а соседние элементы добавляются на текущем узле.

Почему это важно

Изменяемые поля на уровне класса — скрытый источник связности между экземплярами. В деревьях это может незаметно испортить структуру или запустить бесконечную рекурсию при вставке. Даже опытные Python‑разработчики временами забывают, что списки и словари, объявленные у класса, являются общими для всех экземпляров, если их явно не переопределить в конструкторе.

Этот паттерн не привязан к разбору плана счетов. Любой алгоритм, который постепенно строит вложенные структуры по порядку или по отступам, опирается на контейнеры на уровне узлов. Правильно проведённая граница — это разница между аккуратной иерархией и падением со стектрейсом.

Итоги

Если рекурсивная вставка неожиданно зацикливается, проверьте два момента в самом начале. Во‑первых, действительно ли ветвление меняется между вызовами. Во‑вторых, убедитесь, что все контейнеры, которые должны быть у каждого экземпляра, инициализируются в конструкторе, а не на уровне класса. В Python списки и словари, объявленные в области класса, общие для всех экземпляров и ломают логику, зависящую от состояния, вроде построения деревьев. Переместите их в __init__, упростите правила вставки — и иерархия сложится ровно так, как подсказывают данные.