recursion.md

Рекурсия

Многие алгоритмы очень красиво и компактно записываются в рекурсивной форме. Сортировки, обходы графов, строковые алгоритмы.

Однако рекурсия требует места для хранения промежуточного состояния — на куче или в стеке. Конечно, есть хвостовая рекурсия, которая естественным образом может быть оптимизирована в цикл. Но это не гарантировано стандартом. Да и не всегда рекурсия именно хвостовая.

Stack overflow не совсем неопределенное поведение, но точно не то, чего хочется видеть на боевом стенде. Потому в серьезных приложениях предпочитают итеративные алгоритмы рекурсивным. Если, конечно, нет гарантии, что глубина рекурсии мала.

В деле искоренения рекурсии из своей программы нужно быть очень внимательным. И не только в корректной имплементации алгоритмов. Помимо алгоритмов, рекурсивными могут быть и структуры данных. И тут в игру вступает RAII, правила нуля, порядок вызовов деструкторов и noexcept.

struct Node {
    int value = 0;
    std::vector<Node> childrens;
};

Такая структура совершенно законна для определения дерева, компилируется и работает. И может быть удобнее, чем вариант с умными указателями.

Нам не нужно никак вручную управлять ресурсами, вектор позаботится обо всем самостоятельно. Пользуемся «правилом нуля» и не пишем ни деструктор, ни конструктора копирования, ни оператора перемещения/копирования, ничего — красота!

Однако, деструктор, сгенерированный компилятором, будет рекурсивным! И при слишком большой глубине дерева мы получим переполнение стека.

Хорошо, пишем свой деструктор: нам нужна очередь, чтобы обойти вершины дерева... А очередь это аллокация памяти. А аллокация памяти — операция, бросающая исключения. И вот у нас деструктор будет бросать исключения. Что совсем не хорошо.

Можно написать деструктор без аллокаций и рекурсии. Но его алгоритмическая сложность будет квадратичной:

1. Находим вершину, у которой последний элемент в векторе потомков является листом.
2. Удаляем этот элемент из вектора.
3. Повторяем, пока дерево не закончится

Для обычного связанного списка проблема также сохраняется

struct List {
    int value = 0;
    std::unique_ptr<List> next;
};

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

Так что пишем деструктор, а вместе с ним все остальные специальные методы (в данном случае только перемещающие операции)

struct List {
    int value = 0;
    std::unique_ptr<List> next;

    ~List() {
        while (next) {
            // деструктор все также рекурсивен,
            // но теперь глубина рекурсии — 1 вызов
            next = std::move(next->next);
        }
    }

    List() noexcept = default;
    List(List&&) noexcept = default;
    List& operator=(List&&) noexcept = default;
};

---

С рекурсивными структурами данных в C++ нужно быть очень аккуратными. Не просто так в Rust написать их «очевидным» способом тяжело.