Рекурсия

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

Проблему можно решить двумя способами. Первый - запомнить цифры в некотором массиве в том порядке, как они получались, а затем напечатать их в обратном порядке; так это и было сделано в функции 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.

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

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