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

4.10 Рекурсия

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.

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

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

Оглавление книги


Генерация: 0.222. Запросов К БД/Cache: 2 / 0
поделиться
Вверх Вниз