Рекурсия и эффективность алгоритмов
💻 Информатика · 11 класс
Что такое рекурсия
Рекурсия — это способ описания процесса или объекта через самого себя. В программировании рекурсивным называют алгоритм, который в ходе своей работы обращается к самому себе для решения такой же, но более простой задачи. Рекурсия позволяет коротко и наглядно записывать вычисления, которые иначе потребовали бы громоздких циклов.
Базовый случай и шаг рекурсии
Любой правильный рекурсивный алгоритм состоит из двух частей.
- Базовый случай — простейшая ситуация, которая решается напрямую, без обращения к себе. Он останавливает рекурсию.
- Шаг рекурсии — сведение задачи к более простой того же вида с повторным вызовом алгоритма.
Классический пример — вычисление факториала числа. По определению n! = n * (n-1)!, а 0! = 1.
факт(n) = 1, если n = 0
факт(n) = n * факт(n-1), если n > 0
Чтобы посчитать факт(3), алгоритм вызывает факт(2), тот — факт(1), тот — факт(0). Дойдя до базового случая, вычисления разворачиваются обратно: 1, 1, 2, 6.
Частая ошибка: забыть базовый случай или неправильно его задать. Тогда алгоритм вызывает себя бесконечно, пока не переполнится память. У каждой рекурсии должно быть условие остановки.
Эффективность алгоритмов
Одну и ту же задачу можно решить разными алгоритмами, и они различаются по затратам времени и памяти. Эффективность алгоритма оценивают по числу основных операций в зависимости от размера входных данных n. Чем медленнее растёт это число при увеличении n, тем алгоритм лучше для больших данных.
| Задача | Рост числа операций | Оценка |
|---|---|---|
| Поиск в неупорядоченном массиве | линейный | пропорционально n |
| Двоичный поиск в упорядоченном | логарифмический | намного быстрее |
| Сравнение всех пар элементов | квадратичный | медленно при больших n |
Пример сравнения
Чтобы найти число в упорядоченном массиве из 1000 элементов, простой перебор может потребовать до 1000 сравнений. Двоичный поиск каждый раз делит область поиска пополам и справится примерно за 10 шагов, ведь 2^10 = 1024. Поэтому при росте данных выбор алгоритма становится важнее скорости компьютера.
Когда применять рекурсию
Рекурсия естественна там, где задача сама определяется через подобные подзадачи: обход дерева каталогов, разбор вложенных структур, сортировки слиянием. При этом каждый вложенный вызов хранится в памяти, поэтому слишком глубокая рекурсия может исчерпать ресурсы — иногда выгоднее заменить её циклом.
Кратко о главном
- Рекурсия — описание алгоритма через обращение к самому себе.
- Рекурсивный алгоритм содержит базовый случай и шаг рекурсии.
- Без условия остановки рекурсия становится бесконечной.
- Эффективность оценивают по росту числа операций при увеличении
n. - Удачный выбор алгоритма важнее быстродействия компьютера при больших данных.