Рекурсия

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


Основные понятия рекурсии

Изменения кадров стека рекурсивных вызовов — на примере factorial(3)
fact(3)Ожидание возврата fact(2) → поместить в стек
↓ вызов
fact(2)Ожидание возврата fact(1) → поместить в стек
↓ вызов
fact(1)Ожидание возврата fact(0) → поместить в стек
↓ вызов
fact(0) = 1Базовое условие! Начинается возврат → извлечь из стека
↑ Возврат слой за слоем (LIFO)

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);

Классические задачи на рекурсию

Факториал

Пример

#include <stdio.h>

/* Рекурсивная реализация факториала
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;
}

Фибоначчи

Пример

#include <stdio.h>

/* Наивная рекурсия: много повторных вычислений, 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;
}

Задача о Ханойской башне

Пример

#include <stdio.h>

/* Рекурсивное решение задачи о Ханойской башне
Переместить 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 включают эту оптимизацию по умолчанию.

Другие расширения