Рекурсия
Рекурсия — это техника программирования, при которой функция прямо или косвенно вызывает себя во время своего определения или выполнения. Основная идея — разбить сложную задачу на более мелкие подзадачи той же структуры.
Основные понятия рекурсии
fact(3) = 3 × fact(2) = 3 × 2 × fact(1) = 3 × 2 × 1 × fact(0) = 3 × 2 × 1 × 1 = 6
Оранжевый блок (базовое условие) → остановить рекурсию и начать возврат | Кадры стека извлекаются в порядке LIFO: последний добавленный возвращается первым
Корректная рекурсивная функция должна содержать два ключевых элемента:
| Элемент | Значение | Пример (факториал) |
|---|---|---|
| Базовое условие | Условие завершения рекурсии, предотвращающее бесконечную рекурсию. | if (n == 0) return 1; |
| Рекурсивное условие | Разбить задачу на меньшие подзадачи и вызвать саму себя. | return n * factorial(n-1); |
Классические задачи на рекурсию
Факториал
Пример
/* Рекурсивная реализация факториала
n! = n × (n-1)!, базовое условие: 0! = 1 */
long long factorial(int n) {
if (n == 0) return 1; /* Базовое условие */
return n * factorial(n - 1); /* Рекурсивное условие */
}
int main() {
printf("5! = %lld\n", factorial(5)); /* Вывод: 120 */
return 0;
}
Фибоначчи
Пример
/* Наивная рекурсия: много повторных вычислений, O(2ⁿ) */
int fib(int n) {
if (n <= 1) return n; /* Базовое условие */
return fib(n-1) + fib(n-2); /* Рекурсивное условие */
}
/* Оптимизация мемоизацией: кэширование вычисленных результатов, O(n) */
#define MAX 100
long long memo[MAX] = {0};
long long fibMemo(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n]; /* Уже вычислено, вернуть напрямую */
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}
int main() {
printf("fib(10) (наивно): %d\n", fib(10)); /* Вывод: 55 */
printf("fibMemo(50) (с мемоизацией): %lld\n", fibMemo(50)); /* Вывод: 12586269025 */
return 0;
}
Задача о Ханойской башне
Пример
/* Рекурсивное решение задачи о Ханойской башне
Переместить n дисков из src в dst с помощью aux
Шаги: переместить n-1 из src→aux, самый большой из src→dst, n-1 из aux→dst */
void hanoi(int n, char src, char aux, char dst) {
if (n == 1) {
printf("Переместить диск 1 из %c в %c\n", src, dst);
return;
}
hanoi(n - 1, src, dst, aux); /* Переместить n-1 дисков из src в aux */
printf("Переместить диск %d из %c в %c\n", n, src, dst);
hanoi(n - 1, aux, src, dst); /* Переместить n-1 дисков из aux в dst */
}
int main() {
printf("Ханойская башня (3 диска):\n");
hanoi(3, 'A', 'B', 'C');
/* Вывод: всего 7 шагов (2³-1), минимальное число шагов = 2ⁿ-1 */
return 0;
}
Рекурсия против итерации
| Измерение | Рекурсия | Итерация |
|---|---|---|
| Читаемость кода | Высокая(Близко к математическому определению) | Иногда не так интуитивно, как рекурсия |
| Эффективность выполнения | Ниже(накладные расходы на стековый кадр) | Повышенный |
| Накладные расходы памяти | Пространство стека O(глубина рекурсии) | O(1) |
| Риск переполнения стека | Да(Когда глубина слишком велика) | Отсутствует |
| Применимые структуры | Естественные рекурсивные структуры, такие как деревья и графы | Линейные структуры, такие как массивы |
Другие расширенияХвостовая рекурсияЭто особая форма рекурсии, в которой рекурсивный вызов является последней операцией, выполняемой в теле функции. Некоторые компиляторы могут оптимизировать хвостовую рекурсию, преобразуя её в эквивалентную итерацию для экономии пространства стека. Однако не все компиляторы C включают эту оптимизацию по умолчанию.