Раздел 16 — Рекурсия и «разделяй и властвуй»

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

• базовый случай — задача настолько мала, что ответ известен сразу: 0! = 1! = 1;
• шаг — ответ выражается через ту же функцию от меньшего аргумента: n! = n · (n − 1)!. Каждый шаг обязан приближать к базовому случаю.

/* n! с выводом входа и выхода: отступ = глубина рекурсии */
unsigned long long factorial(int n, int depth)
{
    printf("%*sfactorial(%d)\n", depth * 2, "", n);
    unsigned long long result = n <= 1 ? 1 : n * factorial(n - 1, depth + 1);
    printf("%*s= %llu\n", depth * 2, "", result);
    return result;
}

factorial(4)
  factorial(3)
    factorial(2)
      factorial(1)
      = 1
    = 2
  = 6
= 24

Вызов factorial(4) не может закончиться, пока не закончится factorial(3), и так до factorial(1). Ответы возвращаются в обратном порядке: 1, 2, 6, 24. (%*s печатает пустую строку шириной depth * 2 — отступ.)

Без базового случая или с шагом, который к нему не ведёт, рекурсия бесконечна: factorial(-1) с условием n == 1 вместо n <= 1 уходит в −2, −3, … пока не кончится стек.

Каждый вызов получает свой кадр в стеке: параметры, локальные переменные, адрес возврата (раздел 7). В примере выше одновременно жили четыре кадра factorial — у каждого своё n. Глубина рекурсии — сколько кадров живёт одновременно; память на рекурсию — глубина × размер кадра.

Стек мал: 8 МБ в Linux, 1 МБ в Windows. Программа examples/16/depth.c считает сумму 1…N рекурсией sum_to(n) = n + sum_to(n − 1); кадр у неё около сотни байтов:

$ ./depth 10000
sum 1..10000 = 50005000
$ ./depth 1000000
Segmentation fault                     (код 139; в Windows программа завершится без сообщения)

Числа Фибоначчи определены рекурсивно: F(0) = 0, F(1) = 1, F(n) = F(n − 1) + F(n − 2). Функция, переписанная прямо с определения, верна, но каждый вызов порождает два, и одни и те же значения считаются снова и снова: fib(5) вызывает fib(3) дважды, fib(2) — трижды.

long long fib(int n)
{
    calls++;
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

fib(10) = 55, calls 177
fib(20) = 6765, calls 21891
fib(30) = 832040, calls 2692537

Число вызовов растёт примерно в 1,6 раза на каждую единицу n — экспоненциально: fib(50) — уже около 40 миллиардов вызовов и минута работы, fib(60) — часы. Мемоизация — запоминать уже посчитанные значения в таблице и не считать их второй раз:

/* С мемоизацией: каждое значение считается один раз; 0 в таблице — «ещё не посчитано» */
long long fib_memo(int n)
{
    static long long memo[93];
    calls++;
    if (n < 2) {
        return n;
    }
    if (memo[n] == 0) {
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    }
    return memo[n];
}

fib_memo(90) = 2880067194370816120, calls 179

179 вызовов вместо астрономического числа: O(n). Таблица — static-массив из раздела 15, она обнулена и живёт между вызовами. Размер 93 — F(92) ещё помещается в long long, F(93) уже нет. А простой цикл с двумя переменными считает F(n) тоже за O(n) и без таблицы — рекурсия здесь лишь наглядна, но не нужна.

Рекурсия естественна, когда задача делится на половины. Двоичный поиск из раздела 8 рекурсией: искать в левой или правой половине — та же задача вдвое меньшего размера, глубина — log₂ n:

/* Двоичный поиск в отсортированном a[low..high]: индекс или -1 */
int binary_search(const int a[], int low, int high, int key)
{
    if (low > high) {
        return -1;
    }
    int mid = low + (high - low) / 2;
    if (a[mid] == key) {
        return mid;
    }
    return a[mid] < key ? binary_search(a, mid + 1, high, key) : binary_search(a, low, mid - 1, key);
}

Быстрое возведение в степень: xⁿ = (x^n/2)², при нечётном n — ещё умножить на x. Вместо n − 1 умножений — около 2 log₂ n: 3¹³ — за 7 умножений вместо 12, а x^{1 000 000} — за 40 вместо миллиона.

long long power(long long x, int n)
{
    if (n == 0) {
        return 1;
    }
    long long half = power(x, n / 2);        /* половину считаем один раз */
    return n % 2 == 0 ? half * half : half * half * x;
}
/* 3^13 = 1594323, 2^62 = 4611686018427387904 */

Ключ — half вычисляется один раз. Запись power(x, n / 2) * power(x, n / 2) делает два одинаковых вызова на каждом уровне — та же ошибка, что у Фибоначчи, и снова n умножений.

«Разделяй и властвуй»: разделить задачу на части, решить каждую той же функцией, объединить решения. Сортировка слиянием делит массив пополам, сортирует половины рекурсивно и сливает две отсортированные половины в одну: смотрит на первые элементы обеих, меньший переносит в результат, и так до конца.

/* Слить отсортированные a[left..mid) и a[mid..right) */
void merge(int a[], int left, int mid, int right)
{
    int i = left, j = mid, k = left;
    while (i < mid && j < right) {
        buffer[k++] = a[i] <= a[j] ? a[i++] : a[j++];   /* <= — равные берутся слева: устойчиво */
    }
    while (i < mid) {
        buffer[k++] = a[i++];
    }
    while (j < right) {
        buffer[k++] = a[j++];
    }
    for (k = left; k < right; k++) {
        a[k] = buffer[k];
    }
}

/* Сортировка слиянием a[left..right) */
void merge_sort(int a[], int left, int right)
{
    if (right - left < 2) {         /* 0 или 1 элемент — уже упорядочено */
        return;
    }
    int mid = left + (right - left) / 2;
    merge_sort(a, left, mid);
    merge_sort(a, mid, right);
    merge(a, left, mid, right);
}

source     38 27 43 3 9 82 10
merge      3 9 10 27 38 43 82

• Сложность O(n log n) в любом случае. Массив делится пополам log₂ n раз; на каждом уровне деления все слияния вместе переносят n элементов. Для миллиона это 20 уровней по миллиону — 2·10⁷ действий против 5·10¹¹ у сортировок раздела 8.
• Нужен дополнительный массив размера n (buffer). Пока нет динамической памяти (раздел 17), это глобальный массив наибольшего размера.
• Сортировка устойчива: при равенстве берётся элемент левой половины (<=), и равные сохраняют порядок. С < устойчивость пропадает.
• Отрезки в функциях — полуоткрытые [left, right): так длина равна right − left, а половины [left, mid) и [mid, right) не пересекаются.

Быстрая сортировка (Хоар, 1960) делит иначе: выбирает опорный элемент и разбивает массив так, чтобы слева оказались меньшие опорного, справа — не меньшие, а опорный встал на своё окончательное место. Потом рекурсивно сортирует обе части; сливать ничего не нужно.

/* Разбиение Ломуто: опорный — последний; слева от результата меньшие, справа — не меньшие */
int partition(int a[], int low, int high)
{
    int pivot = a[high];
    int i = low;
    for (int j = low; j < high; j++) {
        if (a[j] < pivot) {
            swap(&a[i], &a[j]);
            i++;
        }
    }
    swap(&a[i], &a[high]);
    return i;
}

void quick_sort(int a[], int low, int high)
{
    if (low >= high) {
        return;
    }
    int p = partition(a, low, high);
    quick_sort(a, low, p - 1);
    quick_sort(a, p + 1, high);
}

source     38 27 43 3 9 82 10
partition of b around 10 -> index 2
           3 9 10 38 27 82 43             (10 на своём месте; левая и правая части ещё не упорядочены)
quick      3 9 10 27 38 43 82

• В среднем O(n log n), и на практике это обычно самая быстрая сортировка сравнениями: работает в том же массиве, без буфера, с простым внутренним циклом.
• В худшем случае O(n²). Если опорный каждый раз оказывается наименьшим или наибольшим, одна часть пуста, а другая меньше всего на 1. С последним элементом в роли опорного так происходит на уже отсортированном массиве — самом частом в жизни. Глубина рекурсии тогда n, и на миллионе элементов программа ещё и переполнит стек.
• Защита — выбор опорного: средний элемент, медиана трёх (первого, среднего, последнего) или случайный. Тогда худший случай становится крайне маловероятным.
• Разбиение Ломуто плохо работает с повторами (равные опорному уходят в одну часть). Разбиение Хоара — два индекса навстречу друг другу, обмен пар «большой слева — маленький справа» — с повторами справляется и в среднем делает втрое меньше обменов. Оно в примере замеров ниже (examples/16/bench.c).
• Быстрая сортировка неустойчива: разбиение переставляет равные элементы.

Оценка O(…) говорит, как растёт время, но не сколько секунд займёт работа. Проверяют замером: функция clock() из time.h возвращает процессорное время программы в «тиках», CLOCKS_PER_SEC тиков в секунде:

memcpy(work, source, n * sizeof work[0]);   /* каждая сортировка получает одни и те же данные */
clock_t start = clock();
sort(work, n);                             /* указатель на функцию сортировки, раздел 15 */
double seconds = (double)(clock() - start) / CLOCKS_PER_SEC;

Замер examples/16/bench.c на сервере курса (gcc -O2; быстрая — Хоар со средним опорным; вставками — до 10⁵):

• При росте n в 10 раз время вставок растёт в 100 раз (0,017 → 1,71) — O(n²); у слияния и быстрой — чуть больше чем в 10 раз — O(n log n). На миллионе разница — 3 минуты против десятой доли секунды.
• На маленьких n все сортировки одинаково мгновенны: асимптотика решает на больших данных. Поэтому библиотечные сортировки внутри коротких отрезков переходят на вставки.
• На отсортированных данных вставки — самые быстрые: O(n), 0,0001 с на 10⁵. Вид данных важен не меньше размера.
• qsort медленнее своей быстрой сортировки по int: каждое сравнение — вызов функции через указатель. Зато она одна на любые типы.
• Замер шумит: повторите несколько раз и берите меньшее время; не замеряйте сборку без оптимизации — в ней относительные цифры другие.

Когда ответ — выбор из многих вариантов (расстановка, маршрут, расписание), его строят по шагам: на каждом шаге пробуют все допустимые продолжения, для каждого рекурсивно строят остальное, а затем отменяют выбор и пробуют следующий. Это перебор с возвратом (backtracking). Все перестановки чисел 1…n:

void permutations(int pos, int n)
{
    if (pos == n) {                      /* перестановка готова — вывести */
        …
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (!used[v]) {
            used[v] = true;
            perm[pos] = v;
            permutations(pos + 1, n);
            used[v] = false;            /* возврат: освободить число для следующих вариантов */
        }
    }
}
/* n = 3: 123 132 213 231 312 321 */

Ферзи: расставить n ферзей на доске n × n так, чтобы никакие два не били друг друга. В каждой строке ровно один ферзь; ставим по строкам, проверяя столбец и диагонали уже поставленных, а если в строке нет безопасной клетки — возвращаемся и двигаем предыдущего (examples/16/backtrack.c):

4 queens: 2 solutions, 60 positions tried (of 4^4)
6 queens: 4 solutions, 894 positions tried (of 6^6)
8 queens: 92 solutions, 15720 positions tried (of 8^8)
10 queens: 724 solutions, 348150 positions tried (of 10^10)

Ветвь отбрасывается, как только в ней появилось противоречие, и её продолжения не перебираются. Поэтому для 8 ферзей проверено 15 720 клеток, а не 8⁸ ≈ 16,7 млн расстановок. Время перебора всё равно растёт экспоненциально, но отсечение делает его посильным для разумных n. Глубина рекурсии — число шагов (n), стек не переполняется.