- 122 -
числовые переменные. Но будут рискованными операции передачи через бестиповый параметр таких данных, как множества или элементы вводимых перечислимых типов, из-за особенностей их машинного представления.
6.9.6.4. Рекурсия. Использование рекурсии — традиционное преимущество языка Паскаль. Турбо Паскаль в полной мере позволяет строить рекурсивные алгоритмы. Под рекурсией понимается вызов функции (процедуры) из тела этой же самой функции (процедуры).
Рекурсивность часто используется в математике. Так, многие определения математических формул рекурсивны. В качестве примера можно привести формулу вычисления факториала:
и целой степени числа:
Видно, что для вычисления каждого последующего значения нужно знать предыдущее. В Паскале рекурсия записывается так же, как и в формулах. Для сравнения рассмотрим реализации функций вычисления того же факториала:
| FUNCTION Fact( n : Word ) : Longlnt;
| BEGIN
| if n=0
| then Fact := 1
| else Fact := n * Fact( n-1 );
| END;
и степени n числа x:
| FUNCTION IntPower( x : Real; n : Word ) : Real;
| BEGIN
| if n=0
| then IntPower := 1
| else IntPower := x * IntPower( x, n-1);
| END;
Если в функцию передаются n>0, то происходит следующее: запоминаются известные значения членов выражения в ветви ELSE (для факториала это n, для степени — x), а для вычисления неизвестных вызываются те же функции, но с «предшествующими»
- 123 -
аргументами. При этом вновь запоминаются (но в другом месте памяти!) известные значения членов и происходят вызовы. Так происходит до тех пор, пока выражение не станет полностью определенным (в наших примерах — это присваивание в ветви THEN), после чего алгоритм начинает «раскручиваться» в обратную сторону, изымая из памяти «отложенные» значения. Поскольку при этом на каждом очередном шаге все члены выражений уже будут известны, через n таких, «обратных» шагов мы получим конечный результат.
Необходимым для работоспособности рекурсивных процедур является наличие условия окончания рекурсивных вызовов (например, проверка значения изменяющегося параметра). Действия, связанные с такой проверкой, уже не могут содержать рекурсивных вызовов. Если это условие не будет выполняться, то глубина рекурсии станет бесконечной, что неизбежно приведет к аварийному останову программы.
Зачастую внесение рекурсивности в программы придает им изящность. Но всегда оно же «заставляет» программы расходовать больше памяти. Дело в том, что каждый «отложенный» вызов функции или процедуры — это свой набор значений всех локальных переменных этой функции, размещенных в стеке. Если будет, например, 100 рекурсивных вызовов функции, то в памяти должны разместиться 100 наборов локальных переменных этой функции. В Турбо Паскале размер стека (он регулируется первым параметром директивы компилятора $M) не может превышать 64К — а это не так уж много.
Несмотря на наглядность рекурсивных описаний, во многих случаях те же задачи более эффективно решаются итерационными методами, не требующими «лишней» памяти при сопоставимой скорости вычислений. Например, функция вычисления целой степени числа X может быть переписана следующим образом:
| FUNCTION IntPower(x : Real; n : Word ) : Real;
| VAR
| i : Word; m : Real;
| BEGIN
| m : = 1;
| for i:=1 to n do
| m:=m*x;
| IntPower := m
| END;
Примечательно, что даже компилятор чисто рекурсивного языка Turbo Prolog везде, где только можно, старается преобразовать рекурсию в итерационные действия.
Отметим, что в общем случае класс функций вида
- 124 -
всегда может быть запрограммирован итеративно (что и советуем делать). В то же время существует ряд приложений, таких, например, как грамматический разбор символьных конструкций, где рекурсия уместна и эффективна.
В заключение несколько слов о работе оператора Exit в рекурсивных процедурах. Он срабатывает всегда на один «уровень» глубины рекурсии. Таким образом, выйти из рекурсивной подпрограммы до ее естественного завершения довольно непросто.
Все сказанное выше будет также верно и для так называемой косвенной рекурсии — когда подпрограмма A вызывает подпрограмму B, а в B содержится вызов A. Только расход памяти будет еще больше из-за необходимости сохранения локальных переменных B.
6.10. Модули. Структура модулей
Модуль (UNIT) в Турбо Паскале — это специальным образом оформленная библиотека определений типов, констант, переменных, а также процедур и функций. Модуль в отличие от программы не может быть запущен на выполнение самостоятельно: он может только участвовать в построении программы или другого модуля. Но в отличие от фрагментов, подключаемых к программе при компиляции директивой {$1 ИмяФайла}, модули предварительно компилируются независимо от использующей их программы. Результатом компиляции модуля является файл с расширением .TPU (Turbo Pascal Unit). Для того чтобы подключить модуль к программе (или другому модулю), необходимо и достаточно указать его имя в директиве USES.
Все системные библиотеки Турбо Паскаля реализованы как модули, и чтобы воспользоваться, например, библиотеками функций операционной системы DOS и графики Graph, нужно только указать директиву
USES
DOS, Graph;
и дальше использовать любое содержимое библиотек, как будто оно предопределено в языке.
В Турбо Паскале возможность модульного построения чрезвычайно полезна в двух случаях. Во-первых, модули очень удобны для
- 125 -
построения собственных библиотек процедур и функций, которые впоследствии могут подключаться к разным программам, не требуя при этом никаких переделок. Во-вторых, именно модульность позволяет создавать программы практически любого размера. Дело в том, что ни программа, ни модуль, не могут произвести выполнимый код объемом более 64K, если они не используют при построении другие модули. В то же время сумма объемов модулей, составляющих программу, ограничена лишь объемом ОЗУ ПЭВМ, и то, если не используется оверлейная структура. Общая структура модуля приводится на рис. 6.17.
UNIT ИмяМодуля;
INTERFACE ← начало раздела объявлений
USES { используемые при объявлениях модули: }
Имя_Модуля1, Имя_Модуля2, ... ;
CONST Блок объявления библиотечных констант