Рекурсия и рекурсивные алгоритмы
💻 Информатика · 10 класс
Понятие рекурсии
Рекурсия — это способ определения объекта или алгоритма через самого себя. Рекурсивная подпрограмма в ходе своей работы вызывает саму себя, но с другими, более простыми данными. Так сложная задача сводится к такой же, но меньшей задаче, пока не дойдёт до простейшего случая.
Любое корректное рекурсивное определение состоит из двух частей: базовый случай (когда ответ известен сразу, без обращения к себе) и рекурсивный случай (сведение к меньшей задаче). Без базового случая рекурсия не остановится.
Пример: факториал
Факториал числа определяется так: 0! = 1 (база), n! = n * (n-1)! (рекурсия). На языке программирования:
def f(n):
if n == 0:
return 1
return n * f(n-1)
Вызов f(3) приводит к цепочке: 3 * f(2) = 3 * 2 * f(1) = 3 * 2 * 1 * f(0) = 3 * 2 * 1 * 1 = 6.
Как работает вызов
| Шаг | Вычисление |
|---|---|
f(3) | возвращает 3 * f(2) |
f(2) | возвращает 2 * f(1) |
f(1) | возвращает 1 * f(0) |
f(0) | возвращает 1 (база) |
Вызовы накапливаются, пока не достигнут базы, а затем «сворачиваются» обратно, перемножая результаты.
Числа Фибоначчи
Ещё один классический пример: F(1) = F(2) = 1, F(n) = F(n-1) + F(n-2). Рекурсия здесь наглядна, но неэффективна: одни и те же значения вычисляются много раз. Поэтому на практике часто заменяют рекурсию циклом.
Рекурсия и стек вызовов
Каждый незавершённый вызов подпрограммы хранится в особой области памяти — стеке вызовов. При рекурсии в стеке одновременно находятся все вызовы от первого до базового. Поэтому слишком глубокая рекурсия может переполнить стек и привести к ошибке. Это плата за наглядность: рекурсивная запись короче, но требует больше памяти, чем эквивалентный цикл.
Когда применять рекурсию
Рекурсия особенно удобна там, где задача по своей природе самоподобна: обход дерева каталогов, разбор вложенных скобок, построение фракталов, алгоритмы «разделяй и властвуй» (быстрая сортировка, двоичный поиск). В таких случаях рекурсивное решение проще и понятнее цикла.
| Свойство | Рекурсия | Цикл |
|---|---|---|
| Запись | короче и нагляднее | длиннее |
| Память | расходует стек вызовов | экономнее |
| Риск | переполнение стека | зацикливание |
Частые ошибки. Забытый базовый случай — программа уходит в бесконечную рекурсию и аварийно завершается переполнением стека. Неверное сведение, при котором задача не уменьшается. Слишком глубокая рекурсия для больших данных.
Кратко о главном
- Рекурсия — определение алгоритма через вызов самого себя.
- Обязательны базовый случай и сведение к меньшей задаче.
- Классические примеры — факториал и числа Фибоначчи.
- Без базового случая рекурсия бесконечна и переполнит стек.