mirror of
https://github.com/Nekrolm/ubbook.git
synced 2025-12-18 05:14:34 +03:00
71 lines
4.9 KiB
Markdown
71 lines
4.9 KiB
Markdown
# Рекурсия
|
||
|
||
Многие алгоритмы очень красиво и компактно записываются в рекурсивной форме.
|
||
Сортировки, обходы графов, строковые алгоритмы.
|
||
|
||
Однако рекурсия требует места для хранения промежуточного состояния — на куче или в стеке.
|
||
Конечно, есть хвостовая рекурсия, которая естественным образом может быть оптимизирована в цикл. Но это не гарантировано стандартом. Да и не всегда рекурсия именно хвостовая.
|
||
|
||
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 написать их «очевидным» способом тяжело.
|