4.10. Рекурсия

В Си допускается рекурсивное обращение к функциям, т.е. функция может прямо или косвенно обращаться сама к себе. Рассмотрим печать числа в виде строки символов. Как мы упоминали ранее, цифры генерируются в обратном порядке — младшие цифры получаются раньше старших, а печататься они должны в правильной последовательности.

Проблему можно решить двумя способами. Первый — запомнить цифры в некотором массиве в том порядке, как они получались, а затем напечатать их в обратном порядке; так это и было сделано в функции itoa, рассмотренной в параграфе 3.6. Второй способ — воспользоваться рекурсией, при которой printd сначала вызывает себя, чтобы напечатать все старшие цифры, а затем печатает последнюю младшую цифру. Эта программа, как и предыдущий ее вариант, при обработке самого большого по модулю отрицательного числа работает неправильно.

#include <stdio.h>

/* printd: печатает n как целое десятичное число */
void printd(int n)
{
    if (n < 0) {
        putchar('-');
        n = -n;
    }
    if (n / 10)
        printd(n / 10);
    putchar(n % 10 + '0');
}

Когда функция рекурсивно обращается сама к себе, при каждом обращении она получает новый полный набор автоматических переменных, независимых от предыдущих наборов. Так, в обращении printd(123) при первом вызове аргумент n = 123, при втором — printd получает аргумент 12, при третьем вызове — значение 1. Функция printd на третьем уровне вызова печатает 1 и возвращается на второй уровень, после чего печатает цифру 2 и возвращается на первый уровень. Здесь она печатает 3 и заканчивает работу.

Другой хороший пример рекурсии — это быстрая сортировка, предложенная Ч.А.Р. Хоаром в 1962 г. Для заданного массива выбирается один элемент, который разбивает остальные элементы на два подмножества — те, что меньше, и те, что не меньше него. Та же процедура рекурсивно применяется и к двум полученным подмножествам. Если в подмножестве менее двух элементов, то сортировать нечего и рекурсия завершается.

Наша версия быстрой сортировки, разумеется, не самая быстрая среди всех возможных, но зато одна из самых простых. В качестве делящего элемента мы используем серединный элемент.

/* qsort: сортирует v[left]...v[right] по возрастанию */
void qsort(int v[], int left, int right)
{
    int i, last;
    void swap(int v[], int i, int j);

    if (left >= right)    /* если в массиве менее двух элементов */
        return;              /* ничего не делается */
    swap(v, left, (left+right)/2);   /* делящий элемент */
    last = left;                     /* переносится в v[0] */
    for(i = left+1; i <= right; i++) /* деление на части */
        if (v[i] < v[left])
            swap(v, ++last, i);
    swap(v, left, last);  /* перезапоминаем делящий элемент */
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

В нашей программе операция перестановки оформлена в виде отдельной функции swap, поскольку она встречается в qsort трижды.

/* swap: поменять местами v[i] и v[j] */
void swap(int v[], int i, int j)
{
    int temp;

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

В стандартной библиотеке есть функция qsort, позволяющая сортировать объекты любого типа.

Рекурсивная программа не обеспечивает ни экономии памяти, поскольку требуется где-то поддерживать стек значений, подлежащих обработке, ни быстродействия; но по сравнению со своим нерекурсивным эквивалентом она часто короче и намного легче для написания и понимания. Такого рода программы особенно удобны для обработки рекурсивно определяемых структур данных вроде деревьев; с хорошим примером на эту тему вы познакомитесь в параграфе 6.5.