Исполняемые доки C: рекурсия

Q: Что такое рекурсия в C?

Функция, которая вызывает саму себя, чтобы решить меньшую версию той же задачи. Любой рекурсивной функции нужны две вещи: базовый случай, который возвращает результат без рекурсии, и рекурсивный случай, который заметно приближается к нему. Без базового случая вызовы никогда не прекратятся и программа упадёт с переполнением стека.

Q: Как написать функцию факториала на C?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Базовый случай обрабатывает 0 и 1, а каждый рекурсивный вызов уменьшает n на единицу, пока не дойдёт до него. Учтите, что int переполняется уже на 13! - для больших значений берите unsigned long long.

Q: Почему рекурсивный Фибоначчи такой медленный в C?

Потому что fib(n) вызывает fib(n-1) и fib(n-2), которые снова и снова пересчитывают одни и те же подзадачи - число вызовов растёт экспоненциально, поэтому fib(50) считался бы годами. Переписанный в виде цикла, хранящего два последних значения, он становится линейным и мгновенным.

Q: Из-за чего происходит переполнение стека при рекурсии в C?

Каждый вызов занимает кадр стековой памяти под параметры и локальные переменные, а стек - это всего несколько мегабайт. Отсутствующий или недостижимый базовый случай означает бесконечную рекурсию и мгновенное падение; даже корректная рекурсия глубиной в сотни тысяч уровней способна исчерпать стек.

Функция, которая вызывает саму себя

Ничто не мешает функции на C вызвать саму себя. Её собственное имя видно внутри её тела, поэтому вот такой код совершенно законен:

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* вызывает себя - но никогда не останавливается! */
}

И он же сломан. Он печатает бесконечно, уходя в отрицательные числа, пока программа не упадёт. Ему не хватает базового случая: условия, при котором функция возвращается без вызова самой себя.

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* базовый случай: остановка */
        printf("Взлёт!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* рекурсивный случай: задача поменьше */
}

int main(void) {
    countdown(5);
    return 0;
}

У любой рекурсивной функции есть ровно эти две части:

Базовый случай - наименьший вход, на который ответ даётся напрямую, без дальнейших вызовов.
Рекурсивный случай - решает задачу через строго меньшую версию самой себя.

Именно со «строго меньшей» люди ошибаются. countdown(n - 1) при каждом вызове движется к 0. countdown(n) - нет, и countdown(n / 2) тоже не двигался бы, если n могло бы вечно оставаться 1. Каждый путь обязан уменьшать задачу, иначе базовый случай никогда не будет достигнут.

Факториал

Стандартный первый пример. n! - это n × (n-1) × ... × 1, а 0! по определению равен 1. Само определение уже рекурсивно: n! = n × (n-1)!.

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* базовый случай: 0! и 1! оба равны 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* рекурсивный случай */
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    printf("20! = %llu\n", factorial(20));
    return 0;
}

Проследите factorial(4), чтобы увидеть, как собирается ответ. Вызовы идут вниз, а умножения происходят на обратном пути вверх:

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (базовый случай)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

Ничего не умножается, пока не вернётся базовый случай. Каждый отложенный вызов ждёт, храня своё собственное n, - и вот это стоит усвоить: ожидающие вызовы занимают память.

Обратите внимание на тип возвращаемого значения. int переполняется примерно на 13!, молча выдавая неверное число, - C ничего не проверяет. unsigned long long доводит вас до 20! и не дальше, потому что 21! не влезает в 64 бита. Ограничивает здесь не рекурсия, а тип.

Базовый случай намеренно написан как n <= 1, а не n == 1: factorial(0) должен быть 1, и <= это обеспечивает. С n == 1 вызов factorial(0) ушёл бы в рекурсию к -1, -2 и никогда бы не завершился - отличная иллюстрация того, как «очевидно правильный» базовый случай может пропустить один из входов.

Фибоначчи и почему наивная версия - ловушка

Фибоначчи - другая классика: каждое число равно сумме двух предыдущих, начиная с 0 и 1. Рекурсивное определение пишется само собой.

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (вызовов: %lld)\n", n, result, calls);
    }
    return 0;
}

Посмотрите на счётчики вызовов. fib(10) обходится в 177 вызовов; fib(35) - почти в 30 миллионов. Каждый шаг на 5 умножает работу примерно на одиннадцать.

Причина видна в дереве вызовов. fib(5) вызывает fib(4) и fib(3); fib(4) вызывает fib(3) ещё раз; и каждый из них заново считает fib(2) с нуля. Ничего не запоминается, поэтому одни и те же подзадачи решаются снова и снова, а число вызовов растёт примерно как 1,6ⁿ. fib(50) таким способом считался бы днями; fib(100) пережил бы вселенную.

Версия с циклом хранит два последних значения и линейна:

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

fib(90) возвращается мгновенно. Урок не в том, что «рекурсия медленная», - а в том, что медленна рекурсия с перекрывающимися подзадачами, если только вы не запоминаете ответы. Сохраняйте результаты в массив по мере вычисления (мемоизация), и рекурсивная версия тоже станет линейной.

Стек вызовов и переполнение стека

Каждому вызову функции нужно где-то держать свои параметры, локальные переменные и адрес возврата. Это хранилище называется кадром стека: он кладётся на стек при начале вызова и снимается при возврате. Рекурсия складывает кадры один поверх другого - у factorial(1000) одновременно живёт тысяча кадров, и у каждого своё n.

Стек невелик. Типичное значение по умолчанию - от 1 до 8 МБ, так что реальный предел это несколько десятков тысяч кадров, а если каждый кадр держит большой локальный массив - куда меньше. Превысите его, и программа умрёт:

Segmentation fault (core dumped)

Это и есть переполнение стека, и получить его можно двумя способами:

Бесконечная рекурсия - отсутствующий или недостижимый базовый случай. Это баг, и падение наступает немедленно:

int bad(int n) {
    return bad(n - 1);      /* нет базового случая - падение за доли секунды */
}

Корректная, но слишком глубокая - по одному вызову на элемент списка из миллиона элементов. Логика верна, подход не влезает в стек. Перепишите циклом или перестройте так, чтобы глубина стала логарифмической (рекурсия по половинам, как у двоичного поиска и сортировки слиянием, даёт глубину около 20 для миллиона элементов).

Некоторые компиляторы умеют превращать хвостовую рекурсию - когда рекурсивный вызов это самое последнее, что делает функция, и после него не остаётся отложенной работы, - в цикл, переиспользуя один кадр. countdown выше хвостово-рекурсивна; factorial - нет, потому что умножение всё равно должно произойти после возврата из вызова. Но C не требует этой оптимизации, так что она может случиться, а может и нет, в зависимости от компилятора и флагов. Никогда не пишите на C код, который работает только потому, что оптимизатор устранил хвостовой вызов.

Где рекурсия действительно выигрывает

Любую рекурсивную функцию можно переписать циклом, и для простого счёта цикл заведомо лучше. Рекурсия окупается, когда рекурсивны сами данные - когда структура содержит уменьшенные копии самой себя.

Двоичный поиск - чистый пример: ищем в половине, потом в половине от неё.

#include <stdio.h>

/* возвращает индекс target или -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* базовый случай: ничего не осталось */
    }
    int mid = low + (high - low) / 2;       /* защита от переполнения на больших индексах */

    if (a[mid] == target) {
        return mid;                         /* базовый случай: нашли */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> индекс %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

Здесь два базовых случая, и это нормально: один на успех, другой на исчерпание. Глубина примерно log₂(n), так что даже миллиарду элементов хватит тридцати кадров.

Другие места, где рекурсия естественна: обход дерева или связного списка, обход каталогов, разбор вложенных выражений и сортировки типа «разделяй и властвуй» вроде быстрой сортировки и сортировки слиянием. Во всех этих случаях рекурсивный код короче и понятнее, чем цикл с явным стеком, который его заменяет.

Рекурсия или цикл?

Используйте цикл           когда задача линейна - счёт, суммирование, обход
Используйте рекурсию       когда данные вложены - деревья, вложенные структуры, разделяй и властвуй
Перепишите рекурсию        если глубина может неограниченно расти вместе с размером входа
Никогда не рекурсию        когда подзадачи перекрываются, если только вы не мемоизируете

Два практических замечания. Рекурсивный вызов стоит чуть дороже итерации цикла - каждый раз нужно положить и снять кадр, - поэтому для горячих простых циклов итеративная версия выигрывает и по скорости, и по памяти. И отладка выглядит иначе: трассировка стека из глубокой рекурсии - это сотни одинаковых на вид кадров, поэтому печатайте параметр при входе (как это делает счётчик calls выше), когда что-то не завершается.

Как писать рекурсивную функцию: чек-лист

Сначала найдите базовый случай. Каков наименьший вход и каков ответ на него? Если вы не можете его назвать, функцию написать нельзя.
Считайте, что рекурсивный вызов работает. Не прослеживайте его мысленно - доверьтесь, что factorial(n - 1) вернёт (n-1)!, и напишите тот единственный шаг, который превращает это в ответ.
Проверьте, что каждый путь уменьшается. Каждый рекурсивный вызов обязан двигаться к базовому случаю при любом возможном входе, включая 0 и отрицательные числа.
Проверьте глубину. Примерно сколько кадров получится на реальных данных? Тысячи - нормально, миллионы - нет.
Проверьте перекрытия. Если одна и та же подзадача считается дважды, нужна мемоизация или цикл.

Часто задаваемые вопросы

Что такое рекурсия в C?

Функция, которая вызывает саму себя, чтобы решить меньшую версию той же задачи. Любой рекурсивной функции нужны две вещи: базовый случай, который возвращает результат без рекурсии, и рекурсивный случай, который заметно приближается к нему. Без базового случая вызовы никогда не прекратятся и программа упадёт с переполнением стека.

Как написать функцию факториала на C?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Базовый случай обрабатывает 0 и 1, а каждый рекурсивный вызов уменьшает n на единицу, пока не дойдёт до него. Учтите, что int переполняется уже на 13! - для больших значений берите unsigned long long.

Почему рекурсивный Фибоначчи такой медленный в C?

Потому что fib(n) вызывает fib(n-1) и fib(n-2), которые снова и снова пересчитывают одни и те же подзадачи - число вызовов растёт экспоненциально, поэтому fib(50) считался бы годами. Переписанный в виде цикла, хранящего два последних значения, он становится линейным и мгновенным.

Из-за чего происходит переполнение стека при рекурсии в C?