Рекурсия

4.10. Рекурсия.

В языке “C” функции могут использоваться рекурсивно; это

означает, что функция может прямо или косвенно обращаться к

себе самой. Традиционным примером является печать числа в

виде строки символов. как мы уже ранее отмечали, цифры гене-

рируются не в том порядке: цифры младших разрядов появляются

раньше цифр из старших разрядов, но печататься они должны в

обратном порядке.

Эту проблему можно решить двумя способами. Первый спо-

соб, которым мы воспользовались в главе 3 в функции ITOA,

заключается в запоминании цифр в некотором массиве по мере

их поступления и последующем их печатании в обратном поряд-

ке. Первый вариант функции PRINTD следует этой схеме.

PRINTD(N) /* PRINT N IN DECIMAL */

INT N;

{

CHAR S[10];

INT I;

IF (N < 0) {

PUTCHAR('-');

N = -N;

}

I = 0;

DO {

S[I++] = N % 10 + '0'; /* GET NEXT CHAR */

} WHILE ((N /= 10) > 0); /* DISCARD IT */

WHILE (--I >= 0)

PUTCHAR(S[I]);

}

Альтернативой этому способу является рекурсивное реше-

ние, когда при каждом вызове функция PRINTD сначала снова

обращается к себе, чтобы скопировать лидирующие цифры, а за-

тем печатает последнюю цифру.

PRINTD(N) /* PRINT N IN DECIMAL (RECURSIVE)*/

INT N;

(

INT I;

IF (N < 0) {

PUTCHAR('-');

N = -N;

}

IF ((I = N/10) != 0)

PRINTD(I);

PUTCHAR(N % 10 + '0');

)

·     95 -

Когда функция вызывает себя рекурсивно, при каждом обра-

щении образуется новый набор всех автоматических переменных,

совершенно не зависящий от предыдущего набора. Таким обра-

зом, в PRINTD(123) первая функция PRINTD имеет N = 123. Она

передает 12 второй PRINTD, а когда та возвращает управление

ей, печатает 3. Точно так же вторая PRINTD передает 1

третьей (которая эту единицу печатает), а затем печатает 2.

Рекурсия обычно не дает никакой экономиии памяти, пос-

кольку приходится где-то создавать стек для обрабатываемых

значений. Не приводит она и к созданию более быстрых прог-

рамм. Но рекурсивные программы более компактны, и они зачас-

тую становятся более легкими для понимания и написания. Ре-

курсия особенно удобна при работе с рекурсивно определяемыми

структурами данных, например, с деревьями; хороший пример

будет приведен в главе 6.

Упражнение 4-7.

Приспособьте идеи, использованные в PRINTD для рекурсив-

ного написания ITOA; т.е. Преобразуйте целое в строку с по-

мощью рекурсивной процедуры.

Упражнение 4-8.

Напишите рекурсивный вариант функции REVERSE(S), которая

располагает в обратном порядке строку S.

4.11. Препроцессор языка “C”.

В языке “с” предусмотрены определенные расширения языка

с помощью простого макропредпроцессора. одним из самых расп-

ространенных таких расширений, которое мы уже использовали,

является конструкция #DEFINE; другим расширением является

возможность включать во время компиляции содержимое других

файлов.

4.11.1. Включение файлов

Для облегчения работы с наборами конструкций #DEFINE и

описаний (среди прочих средств) в языке “с” предусмотрена

возможность включения файлов. Любая строка вида

#INCLUDE “FILENAME”

заменяется содержимым файла с именем FILENAME. (Кавычки обя-

зательны). Часто одна или две строки такого вида появляются

в начале каждого исходного файла, для того чтобы включить

общие конструкции #DEFINE и описания EXTERN для глобальных

переменных. Допускается вложенность конструкций #INCLUDE.

Конструкция #INCLUDE является предпочтительным способом

связи описаний в больших программах. Этот способ гарантиру-

ет, что все исходные файлы будут снабжены одинаковыми опре-

делениями и описаниями переменных, и, следовательно, исклю-

чает особенно неприятный сорт ошибок. Естественно, когда ка-

кой-TO включаемый файл изменяется, все зависящие от него

файлы должны быть перекомпилированы.

·     96 -

4.11.2. Макроподстановка

Определение вида

#DEFINE TES 1

приводит к макроподстановке самого простого вида - замене

имени на строку символов. Имена в #DEFINE имеют ту же самую

форму, что и идентификаторы в “с”; заменяющий текст совер-

шенно произволен. Нормально заменяющим текстом является ос-

тальная часть строки; длинное определение можно продолжить,

поместив \ в конец продолжаемой строки. “Область действия”

имени, определенного в #DEFINE, простирается от точки опре-

деления до конца исходного файла. имена могут быть переопре-

делены, и определения могут использовать определения, сде-

ланные ранее. Внутри заключенных в кавычки строк подстановки

не производятся, так что если, например, YES - определенное

имя, то в PRINTF(“YES”) не будет сделано никакой подстанов-

ки.

Так как реализация #DEFINE является частью работы

маKропредпроцессора, а не собственно компилятора, имеется

очень мало грамматических ограничений на то, что может быть

определено. Так, например, любители алгола могут объявить

#DEFINE THEN

#DEFINE BEGIN {

#DEFINE END ;}

и затем написать

IF (I > 0) THEN

BEGIN

A = 1;

B = 2

END

Имеется также возможность определения макроса с аргумен-

тами, так что заменяющий текст будет зависеть от вида обра-

щения к макросу. Определим, например, макрос с именем MAX

следующим образом:

#DEFINE MAX(A, B) ((A) > (B) ? (A) : (B))

когда строка

X = MAX(P+Q, R+S);

будет заменена строкой

X = ((P+Q) > (R+S) ? (P+Q) : (R+S));

Такая возможность обеспечивает “функцию максимума”, которая

расширяется в последовательный код, а не в обращение к функ-

ции. При правильном обращении с аргументами такой макрос бу-

дет работать с любыми типами данных; здесь нет необходимости

в различных видах MAX для данных разных типов, как это было

бы с функциями.

·     97 -

Конечно, если вы тщательно рассмотрите приведенное выше

расширение MAX, вы заметите определенные недостатки. Выраже-

ния вычисляются дважды; это плохо, если они влекут за собой

побочные эффекты, вызванные, например, обращениями к функци-

ям или использованием операций увеличения. Нужно позаботить-

ся о правильном использовании круглых скобок, чтобы гаранти-

ровать сохранение требуемого порядка вычислений. (Рассмотри-

те макрос

#DEFINE SQUARE(X) X * X

при обращении к ней, как SQUARE(Z+1)). Здесь возникают даже

некоторые чисто лексические проблемы: между именем макро и

левой круглой скобкой, открывающей список ее аргументов, не

должно быть никаких пробелов.

Тем не менее аппарат макросов является весьма ценным.

Один практический пример дает описываемая в главе 7 стандар-

тная библиотека ввода-вывода, в которой GETCHAR и PUTCHAR

определены как макросы (очевидно PUTCHAR должна иметь аргу-

мент), что позволяет избежать затрат на обращение к функции

при обработке каждого символа.

Другие возможности макропроцессора описаны в приложении

А.

Упражнение 4-9.

Определите макрос SWAP(X, Y), который обменивает значе-

ниями два своих аргумента типа INT. (В этом случае поможет

блочная структура).

·     98 -

5.Указатели и массивы

Указатель - это переменная, содержащая адрес другой пе-

ременной. указатели очень широко используются в языке “C”.

Это происходит отчасти потому, что иногда они дают единст-

венную возможность выразить нужное действие, а отчасти пото-

му, что они обычно ведут к более компактным и эффективным

программам, чем те, которые могут быть получены другими спо-

собами.

Указатели обычно смешивают в одну кучу с операторами

GOTO, характеризуя их как чудесный способ написания прог-

рамм, которые невозможно понять. Это безусловно спрAведливо,

если указатели используются беззаботно; очень просто ввести

указатели, которые указывают на что-то совершенно неожидан-

ное. Однако, при определенной дисциплине, использование ука-

зателей помогает достичь ясности и простоты. Именно этот ас-

пект мы попытаемся здесь проиллюстрировать.

Похожие работы

Анализ обыденного языка: общая характеристика направления

Скачать

48443

0

0

... основаниям. При этом философская абстракция языка оказывается неразрывно связана с основными темами и движениями философии в целом. Более конкретно, на ранние стадии традиционно рассматриваемого в рамках АФ анализа обыденного языка глубокое влияние оказала философия Дж. Э. Мура, особенно его учение о здравом смысле, согласно которому такие понятия, как «человек», «мир», «я», «внешний мир», « ...

Русский язык в современной Молдове

Скачать

43709

0

0

... и других странах СНГ, а также облегчение доступа к русской и мировой культуре и науке. Таким образом, судя по данным наших исследований, востребованность русского языка осталась в республике достаточно высокой. Многие представители современной молдавской молодежи продолжают, как их отцы и деды, тянуться к русской культуре, научным и техническим достижениям России. Русский язык остается языком ...

Неиндоевропейские языки

Скачать

39778

0

1

... рисуночное словесно-слоговое письмо). Памятники среднеэламского периода (14—12 вв. до н.э.) выполнены аккадской клинописью. Памятники новоэламского периода относятся к 8—6 вв. до н.э. Был официальным языком в персидском государстве Ахеменидов в 6—4 вв. предполагается, что он, подвергшись влиянию древнеперсидского, сохранился до раннего средневековья. 7. Бурушаски язык Язык бурушаски ( ...

Индоевропейские языки

Скачать

64931

0

0

... /диалект), скифский, согдийский, среднеперсидский, таджикский, таджриши (язык/диалект), талышский, татский, хорезмийский, хотаносакский, шугнано-рушанская группа языков, ягнобский, язгулямский и др. Они относятся к индоиранской ветви индоевропейских языков. Области распространения: Иран, Афганистан, Таджикистан, некоторые районы Ирака, Турции, Пакистана, Индии, Грузии, Российской Федерации. Общее ...