6.9.6.3. Параметры-переменные без типа. Процедуры и функции могут содержать в своих заголовках параметры-переменные без указания их типа, т.е. просто указываются имена параметров без двоеточий и следующих за ними идентификаторов типа. Примеры таких заголовков:
PROCEDURE PDemo ( VAR V1,V2 );
FUNCTION FDemo ( A : Integer; VAR V ) : Real;
Бестиповыми могут быть только параметры-переменные (т.е. те, которые передаются как адрес, а не как значение). Объявленные выше переменные V1, V2 и V могут иметь любой тип. Через них можно передавать подпрограммам строки, массивы, записи или другие данные. Но при этом процедура или функция должна явно задавать тип, к которому внутри нее приравниваются бестиповые переменные. Рассмотрим пример функции, суммирующей N элементов произвольных одномерных числовых массивов (рис. 6.16).
| PROGRAM Demo_Sum;
| VAR
| B1 : Array [-100.. 100] of Byte;
| B2 : Array [ 0 .. 999] of Byte;
| B3 : Array [ 'a'..'z'] of Byte;
| S : String;
| {$R-} { выключаем режим проверки индексов массивов }
| FUNCTION Sum( VAR X; N : Word ) : LongInt;
| TYPE
| XType = Array [ 1..1 ] of Byte;
| VAR
| Summa : Longint; i : Word;
| BEGIN
| Summa := 0;
| for i:=1 to N do
| Summa := Summa* XType( X )[i];
| Sum := Summa
| END;
Рис. 6.16
- 121 -
| { $R+} { можно при необходимости восстановить режим }
| BEGIN
| { Заполнение каким-либо образом массивов B1, B2 и B3; }
| ...
| S := '123456789';
| { печать суммы всех значений элементов массива B1 : }
| WriteLn( Sum( B1, 201));
| { сумма элементов B2 с 100-го по 200-й включительно: }
| WriteLn( Sum( B2[100], 101));
| { сумма 10 элементов массива B3, начиная с 'b'-го : }
| WriteLn( Sum( B3['b'], 10));
| {печать суммы кодов символов строки S с '1'-го по '9'-й}
| WriteLn( Sum( S[1], 9));
| END.
Рис 6.16 (окончание)
Как видно, функция Sum не боится несовместимости типов. Но она будет корректно работать только с массивами, элементами которых являются значения типа Byte. Мы сами задали это ограничение, определив тип XType, к которому впоследствии приводим все, что передается процедуре через параметр X. Обращаем внимание на диапазон описания массива XType: 1..1. Если режим компиляции $R имеет знак минус (состояние по умолчанию), то можно обратиться к массиву с практически любым индексом i и будет получен i-й элемент, считая от первого. Мы задаем индексы 1..1 чисто в иллюстративных целях. Можно было записать
| TYPE
ХТуре = Array [ 0..65520 ] of Byte;
забронировав максимальное число элементов (описание типа без объявления переменной не влияет на потребление памяти программой). В таком случае состояние ключа компиляции $R не играет роли. Функция Sum может начать отсчитывать элементы с любого номера (см. рис. 6.16). Можно даже послать в нее строку, и ее содержимое будет принято за байты (а не символы) и тоже просуммировано. Несложно написать обратную процедуру для заполнения произвольной части различных массивов. Надо лишь, чтобы базовый тип этих массивов совпадал с тем, который вводится внутри процедуры для приведения бестипового параметра. И, конечно, вовсе не обязательно ограничиваться одними массивами. Рассмотренный пример можно распространить и на записи, и на ссылки, и на
- 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 -