Брайан Керниган - Язык программирования Си. Издание 3-е, исправленное

#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.

Упражнение 4.12. Примените идеи, которые мы использовали в printd , для написания рекурсивной версии функции itoa ; иначе говоря, преобразуйте целое число в строку цифр с помощью рекурсивной программы.

Упражнение 4.13. Напишите рекурсивную версию функции reverse(s) , переставляющую элементы строки в ту же строку в обратном порядке.

Некоторые возможности языка Си обеспечиваются препроцессором, который работает на первом шаге компиляции. Наиболее часто используются две возможности: #include, вставляющая содержимое некоторого файла во время компиляции, и #define, заменяющая одни текстовые последовательности на другие. В этом параграфе обсуждаются условная компиляция и макроподстановка с аргументами.

Средство #include позволяет, в частности, легко манипулировать наборами #define и объявлений. Любая строка вида

#include " имя-файла "

или

#include ‹ имя-файла ›

заменяется содержимым файла с именем имя-файла . Если имя-файла заключено в двойные кавычки, то, как правило, файл ищется среди исходных файлов программы; если такового не оказалось или имя-файла заключено в угловые скобки ‹ и ›, то поиск осуществляется по определенным в реализации правилам. Включаемый файл сам может содержать в себе строки #include .

Часто исходные файлы начинаются с нескольких строк #include , ссылающихся на общие инструкции #define и объявления extern или прототипы нужных библиотечных функций из заголовочных файлов вроде ‹stdio.h› . (Строго говоря, эти включения не обязательно являются файлами; технические детали того, как осуществляется доступ к заголовкам, зависят от конкретной реализации.)