Рекурсия в C

Урок объясняет рекурсию — функцию, вызывающую саму себя: из чего она состоит, как растёт стек вызовов и почему бесконтрольная рекурсия в C приводит к переполнению стека.

Каждый рекурсивный вызов кладёт на стек новый кадр со своими локальными переменными. Без базового случая стек растёт бесконечно и переполняется — программа падает с ошибкой stack overflow.

Рекурсивная функция решает задачу, сводя её к меньшей версии той же задачи. У любой корректной рекурсии есть две части: базовый случай (когда останавливаемся) и рекурсивный шаг (когда вызываем себя с уменьшенным аргументом). Классика — факториал:

int factorial(int n) {
    if (n <= 1) {        // базовый случай
        return 1;
    }
    return n * factorial(n - 1);   // шаг: задача поменьше
}

Вызов factorial(4) разворачивается так: 4 * factorial(3), тот — 3 * factorial(2), и так до factorial(1), который вернёт 1 без дальнейших вызовов. Затем результаты «схлопываются» обратно.

Как работает под капотом

Каждый вызов функции создаёт на стеке отдельный кадр (frame) со своими параметрами и локальными переменными. Рекурсия складывает эти кадры стопкой, а потом разбирает её:

Раскрутка вниз (вызовы):        Свёртка вверх (возвраты):

  factorial(4)                    factorial(4) = 4*6 = 24
    |  ждёт factorial(3)            ^
    v                               | возвращает 6
  factorial(3)                    factorial(3) = 3*2 = 6
    |  ждёт factorial(2)            ^
    v                               | возвращает 2
  factorial(2)                    factorial(2) = 2*1 = 2
    |  ждёт factorial(1)            ^
    v                               | возвращает 1
  factorial(1) -> базовый -> 1 ----+

Стек растёт вниз с каждым вызовом, потом сворачивается.

Стек ограничен по размеру (обычно несколько мегабайт). Если рекурсия слишком глубокая или у неё нет базового случая, кадры заполнят весь стек — произойдёт переполнение стека, и программа аварийно завершится.

Частые ошибки

• Нет базового случая. Функция вызывает себя бесконечно, стек переполняется — мгновенный крах.
• Аргумент не уменьшается. Если шаг не приближает к базовому случаю, рекурсия не завершится.
• Слишком глубокая рекурсия. Даже корректная рекурсия на десятки тысяч уровней может переполнить стек, тогда как цикл справился бы.
• Повторные вычисления. Наивная рекурсия для чисел Фибоначчи пересчитывает одно и то же экспоненциальное число раз.

Best practices

• Всегда начинайте с базового случая — проверки, которая останавливает рекурсию. Без неё функция не имеет права на существование.
• Убедитесь, что каждый рекурсивный вызов делает аргумент строго ближе к базовому случаю.
• Для глубокой или производительной обработки предпочитайте цикл: в C он не нагружает стек и обычно быстрее.

Рекурсия работает одинаково во всех языках, и логику легко увидеть на Python. Заодно сравним рекурсивный и итеративный варианты.

def factorial(n):
    if n <= 1:              # базовый случай
        return 1
    return n * factorial(n - 1)   # рекурсивный шаг

print("factorial(5) рекурсивно:", factorial(5))

# Тот же результат циклом — без нагрузки на стек (как в C предпочтительнее)
def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print("factorial(5) циклом:    ", factorial_iter(5))

Та же логика на Python ▶ — оба варианта дают 120. В Python глубокая рекурсия тоже упирается в лимит; в C это переполнение стека. Цикл свободен от этой проблемы.

Рекурсия и структуры данных

Хотя для простого повторения цикл предпочтительнее, есть задачи, где рекурсия — самый естественный инструмент. Это всё, что имеет вложенную, древовидную природу: обход файловой системы (папки внутри папок), разбор выражений, работа с деревьями и графами, алгоритмы «разделяй и властвуй» вроде быстрой сортировки. В таких задачах рекурсивный код короче и яснее итеративного, потому что повторяет структуру самих данных. Важный нюанс производительности: некоторые компиляторы умеют превращать «хвостовую рекурсию» (когда рекурсивный вызов — последнее действие функции) обратно в цикл, не нагружая стек. Но полагаться на это в C не стоит — стандарт не гарантирует такую оптимизацию. Поэтому правило простое: рекурсия для вложенных структур, цикл — для линейных повторений.

Итоги

Рекурсия — это функция, вызывающая саму себя, с двумя обязательными частями: базовым случаем и шагом, уменьшающим задачу. Каждый вызов создаёт кадр на стеке; без базового случая или при слишком большой глубине стек переполняется. Рекурсия элегантна для задач с естественной вложенностью (деревья, разбиение), но для простых повторений в C обычно безопаснее и быстрее цикл.