Язык программирования Си - [38]
>#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), переставляющую элементы строки в ту же строку в обратном порядке.
4.11 Препроцессор языка Си
Некоторые возможности языка Си обеспечиваются препроцессором, который работает на первом шаге компиляции. Наиболее часто используются две возможности: #include, вставляющая содержимое некоторого файла во время компиляции, и #define, заменяющая одни текстовые последовательности на другие. В этом параграфе обсуждаются условная компиляция и макроподстановка с аргументами.
4.11.1 Включение файла
Средство #include позволяет, в частности, легко манипулировать наборами #define и объявлений. Любая строка вида
>#include "имя-файла"
или
>#include ‹имя-файла›
заменяется содержимым файла с именем имя-файла. Если имя-файла заключено в двойные кавычки, то, как правило, файл ищется среди исходных файлов программы; если такового не оказалось или имя-файла заключено в угловые скобки ‹ и ›, то поиск осуществляется по определенным в реализации правилам. Включаемый файл сам может содержать в себе строки #include.
Часто исходные файлы начинаются с нескольких строк #include, ссылающихся на общие инструкции #define и объявления extern или прототипы нужных библиотечных функций из заголовочных файлов вроде ‹stdio.h›. (Строго говоря, эти включения не обязательно являются файлами; технические детали того, как осуществляется доступ к заголовкам, зависят от конкретной реализации.)
Средство #include - хороший способ собрать вместе объявления большой программы. Он гарантирует, что все исходные файлы будут пользоваться одними и теми же определениями и объявлениями переменных, благодаря чему предотвращаются особенно неприятные ошибки. Естественно, при внесении изменений во включаемый файл все зависимые от него файлы должны перекомпилироваться.
4.11.2 Макроподстановка
Определение макроподстановки имеет вид:
>#define имя замещающий-текст
Макроподстановка используется для простейшей замены: во всех местах, где встречается лексема имя, вместо нее будет помещен
