, при втором -
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), переставляющую элементы строки в ту же строку в обратном порядке.