Рекурсия
Рекурсия — это способ описать подпрограмму через вызов этой же подпрограммы. Рекурсивный алгоритм обычно решает задачу для исходных данных, сводя её к такой же задаче меньшего размера.
Рекурсивная подпрограмма состоит из двух частей: базового случая и рекурсивного шага. Базовый случай возвращает результат сразу. Рекурсивный шаг изменяет данные так, чтобы следующий вызов был ближе к базовому случаю. Внутри рекурсивной подпрограммы могут использоваться функции, параметры и локальные переменные.
Например, это рекурсивное определение факториала. При вычислении \(F(3)\) программа получает \(3\cdot F(2)\), затем \(2\cdot F(1)\), затем \(1\cdot F(0)\). После достижения базового случая результаты возвращаются в обратном порядке.
```python
def factorial(n):
if n == 0: # базовый случай
return 1
return n * factorial(n - 1) # рекурсивный вызов
```
Вызов factorial(3) возвращает \(3\cdot2\cdot1\cdot1=6\). Каждый вызов имеет собственное значение параметра n.
Рекурсия не обязательно является ошибкой или логической ошибкой. Ошибка возникает, если нет базового случая или данные не приближаются к нему. Тогда вызовы не прекращаются, память для них заканчивается, и программа завершается с ошибкой. Рекурсию также не следует путать с графом вызовов: граф показывает связи между подпрограммами, а рекурсия описывает вызов подпрограммы самой себя.
Что обязательно должно быть в корректной рекурсивной подпрограмме?
Главное
- Рекурсия — это вызов подпрограммой самой себя, прямо или через другие подпрограммы.
- Корректная рекурсия содержит базовый случай и рекурсивный шаг, уменьшающий или упрощающий задачу.
- Результаты рекурсивных вызовов обычно возвращаются после достижения базового случая.