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

int binsearch(int х, int v[], int n)

{

 int low = 0;

 int high = n-1;

 int mid;

}

а не так:

int low, high, mid;

low = 0;

high = n - 1;

В сущности, инициализация автоматической переменной - это более короткая запись инструкции присваивания. Какая запись предпочтительнее - в большой степени дело вкуса. До сих пор мы пользовались главным образом явными присваиваниями, поскольку инициализация в объявлениях менее заметна и дальше отстоит от места использования переменной.

Массив можно инициализировать в его определении с помощью заключенного в фигурные скобки списка инициализаторов, разделенных запятыми. Например, чтобы инициализировать массив days, элементы которого суть количества дней в каждом месяце, можно написать:

int days[] = {31, 28, 31, 30, 31, 30, 31. 31, 30, 31, 30, 31};

Если размер массива не указан, то длину массива компилятор вычисляет по числу заданных инициализаторов; в нашем случае их количество равно 12.

Если количество инициализаторов меньше числа, указанного в определении длины массива, то для внешних, статических и автоматических переменных оставшиеся элементы будут нулевыми. Задание слишком большого числа инициализаторов считается ошибкой. В языке нет возможности ни задавать повторения инициализатора, ни инициализировать средние элементы массива без задания всех предшествующих значений. Инициализация символьных массивов - особый случай: вместо конструкции с фигурными скобками и запятыми можно использовать строку символов. Например, возможна такая запись:

char pattern[] = "ould";

представляющая собой более короткий эквивалент записи

char pattern[] = {'о', 'u', 'l', 'd', '\0'};

В данном случае размер массива равен пяти (четыре обычных символа и завершающий символ '\0').

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] */