Рекурсия

Рекурсия — это процесс, в котором функция вызывает саму себя напрямую или через другие функции. Это мощный инструмент, который позволяет элегантно решать задачи, которые можно разбить на подзадачи того же типа.

Примеры рекурсии

Представим, что у нас есть автомат для продажи кофе. Клиент даёт автомату купюру, автомат готовит кофе и выдаёт сдачу. Сдача выдаётся монетами: 1, 2, 5 или 10 рублей.
Реализуем функцию которая выдаёт сдачу пользователя исходя из остатка денег после продажи кофе.
Принимаем кол-во монет бесконечным.

Задача: реализовать функцию, которая принимает в качестве параметра сумму, которую необходимо отдать пользователю в виде чисел (монет) 1, 2, 5, 10.

#include <iostream> void getChange(int sum) { int coin = 0; // Проверяем номиналы монет от большего к меньшему if (sum >= 10) { // Если сумма больше или равна 10 coin = 10; } else if (sum >= 5) { // Если сумма больше или равна 5 coin = 5; } else if (sum >= 2) { // Если сумма больше или равна 2 coin = 2; } else if (sum >= 1) { // Если сумма больше или равна 1 coin = 1; } if (coin > 0) { // Если найден подходящий номинал std::cout << coin << ' '; // Выводим монету getChange(sum - coin); // Рекурсивный вызов с уменьшенной суммой } } int main() { int amount = 37; std::cout << "Размен суммы " << amount << ": "; getChange(amount); return 0; }

В данном примере, на 15 строке вызывается функция getChange(), вызывется она внутри функции getChange(), получается, что функция вызывает сама себя - это и есть рекурсия!

Ещё пример задачи, где рекурсия применяется наиболее естественно, – это чтение содержимого каталога (директории), включая все вложенные подкаталоги.
Это реальная задача, решаемая при разработке облачного хранилища файлов.

#include <iostream> #include <filesystem> // Для работы с файловой системой // Функция для чтения содержимого каталога void read_directory_contents(const std::string& path) { namespace fs = std::filesystem; // Итерируем по всем элементам в каталоге for (const auto& entry : fs::directory_iterator(path)) { const std::string full_path = entry.path().string(); if (fs::is_directory(entry.status())) { // Если это каталог std::cout << "Каталог: " << full_path << '\n'; read_directory_contents(full_path); // Рекурсивный вызов } else { // Если это файл std::cout << "Файл: " << full_path << '\n'; } } } int main() { // Указанный путь к каталогу const std::string directory_path = "/path"; // Вызов функции для чтения содержимого каталога read_directory_contents(directory_path); return 0; }

Показанная в примере функция вызывает сама себя на строке 12 - это и есть рекурсия!

Пояснение

Библиотека <filesystem>: Используется для работы с файловыми системами в C++ начиная с версии C++17. Она предоставляет удобные инструменты для итерации по каталогам и проверки типов элементов.
Функция read_directory_contents:
- Проходит через каждый элемент в указанном каталоге с помощью объекта std::filesystem::directory_iterator.
- Определяет тип элемента (файл или каталог) с помощью функции std::filesystem::is_directory.
- Если элемент является каталогом, функция вызывается рекурсивно для дальнейшего обхода вложенных каталогов.
- Если элемент — файл, выводится его полный путь.
Пример вызова: В функции main() указывается путь /path, после чего вызывается функция read_directory_contents. Это путь к каталогу, который нужно исследовать. Подставьте реальный путь к вашему каталогу вместо строки "/path".

Этот код выполнит рекурсивную обработку указанного каталога и выведет пути ко всем файлам и подкаталогам.

Простой пример: факториал

int factorial(int n) { if (n <= 1) return 1; // Базовый случай return n * factorial(n - 1); // Рекурсивный случай } cout << factorial(5); // 120

Пошаговое выполнение:

factorial(5)
5 * factorial(4)
5 * (4 * factorial(3))
5 * (4 * (3 * factorial(2)))
5 * (4 * (3 * (2 * factorial(1))))
5 * (4 * (3 * (2 * 1))) = 120

Типы рекурсии

Прямая рекурсия

Функция вызывает себя напрямую.

void directRecursion(int n) { if (n <= 0) return; cout << n << " "; directRecursion(n - 1); }

Косвенная рекурсия

Функции вызывают друг друга по кругу.

void functionA(int n); void functionB(int n) { if (n <= 0) return; cout << "B: " << n << " "; functionA(n - 1); } void functionA(int n) { if (n <= 0) return; cout << "A: " << n << " "; functionB(n - 2); } functionA(5); // A:5 B:3 A:1

Хвостовая рекурсия

Рекурсивный вызов — последняя операция в функции. Может быть оптимизирована компилятором.

int tailFactorial(int n, int accumulator = 1) { if (n <= 1) return accumulator; return tailFactorial(n - 1, n * accumulator); }

Оптимизация: Превращается в цикл, не расходует стек.

Глубина рекурсии и переполнение стека

Каждый рекурсивный вызов сохраняет контекст в стеке. При слишком большой глубине происходит переполнение стека.

Пример опасной рекурсии:

void infiniteRecursion() { infiniteRecursion(); // Бесконечные вызовы }

Как избежать:

Убедитесь, что имеется условие выхода из цикла
Используйте итерацию для очень глубоких рекурсий
Увеличьте размер стека (настройки компилятора)

Мемоизация (оптимизация рекурсии)

Сохранение результатов дорогих вычислений для повторного использования.

Фибоначчи с мемоизацией

#include <unordered_map> unordered_map cache; int fibMemo(int n) { if (n <= 1) return n; if (cache.find(n) != cache.end()) return cache[n]; cache[n] = fibMemo(n - 1) + fibMemo(n - 2); return cache[n]; }

Сложность: O(n) вместо O(2^n).

Преимущества рекурсии

Простота и читаемость: Рекурсивные решения часто более понятны и лаконичны, особенно для задач, которые естественно рекурсивны (например, обход деревьев).
Естественность для некоторых задач: Например, задачи, связанные с деревьями, графами, комбинаторикой.

Недостатки рекурсии

Переполнение стека: Глубокая рекурсия может привести к ошибке.
Неэффективность: Рекурсивные вызовы могут быть медленными из-за накладных расходов на вызов функции.
Сложность отладки: Рекурсивные функции могут быть сложнее для отладки, особенно если глубина рекурсии большая.

Когда использовать рекурсию?

Задачи с естественной рекурсивной структурой: Например, обход деревьев, графов, задачи "разделяй и властвуй".
Когда важна читаемость кода: Рекурсия часто делает код более понятным.
Когда глубина рекурсии невелика: Для задач, где глубина рекурсии не превышает допустимых пределов.

Альтернатива рекурсии: Итерация

Многие рекурсивные задачи можно решить с помощью итерации (циклов). Итеративные решения обычно более эффективны по памяти и времени.

#include <iostream> int factorial_iterative(int n) { int result = 1; for (int i = 1; i <= n; ++i) { result *= i; } return result; } int main() { std::cout << factorial_iterative(5) << std::endl; // Вывод: 120 return 0; }}

Рекурсия — мощный инструмент, но её нужно использовать с осторожностью, учитывая ограничения по глубине и производительности. Для задач с большой глубиной рекурсии лучше использовать итеративные решения.

Функции

Callback-функции

1. Введение в язык C++ 2. Установка компилятора 3. Установка среды разработки (IDE) 4. Структура программы и компиляция 5. Переменные, константы и типы данных 6. Операторы и выражения 7. Ввод и вывод в консоли 8. Условные операторы 9. Логические выражения 10. Циклы 11. Массивы 12. Динамические массивы 13. Указатели в С++ 14. Ссылки в C++ 15. Функции 16. Рекурсия 17. Callback-функции 18. Динамическое выделение памяти 19. Утечки памяти и как их избежать 20. Умные указатели в С++ 21. Парадигмы программирования 22. Структуры (struct) 23. Классы и объекты в C++ 24. Инкапсуляция 25. Наследование 26. Полиморфизм 27. Абстрактные классы 28. Списки инициализации 29. Перегрузка операторов 30. Обработка исключений 31. Пользовательские исключения 32. Шаблонные функции в C++ 33. Шаблонные классы в C++ 34. STL и использование стандартных шаблонов