ubbook/runtime/recursion.md

# Рекурсия

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

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

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

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


```C++
struct Node {
    int value = 0;
    std::vector<Node> children;
};
```

Такая структура совершенно законна для определения дерева, [компилируется и работает](https://godbolt.org/z/evecMd). И может быть удобнее, чем вариант с умными указателями.

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

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

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

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

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


Для обычного связанного списка проблема также сохраняется
```C++
struct List {
    int value = 0;
    std::unique_ptr<List> next;
};
```
Но в этом случае рекурсия является хвостовой и можно надеяться, что оптимизатор справится. Но вы же гоняете тесты и на дебажных сборках, верно?

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

```C++
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 написать их «очевидным» способом тяжело.