При описании рекурсивных функций необходимо хорошо представлять процесс вычислений. Всякая рекурсия состоит из двух этапов: углубление (погружение) внутрь рекурсии и выход из нее. На первом этапе никаких вычислений не производится, а идет только настройка рабочей формулы на конкретные операнды. На втором этапе происходит процесс вычислений по настроенным формулам.
Рассмотрим рекурсивный процесс на примере вычисления факториала для N = 3. Получим следующие шаги:
1) N = 3, где N<>0, следовательно, FACTORIAL:=3*FACTORIAL(2);
2) N = 2, где N<>0, следовательно, FACTORIAL:=2*FACTORIAL(1);
3) N = 1, где N<>0, следовательно, FACTORIAL:=1*FACTORIAL(0);
4) N =0, следовательно, FACTORIAL:=1,
т.е. получили не рекурсивное значение. Углубление в рекурсию закончено, далее пойдет процесс выхода из нее с выполнением необходимых вычислений.
В выражение 1*FACTORIAL(0) вместо FACTORIAL(0) подставляется его значение 1, вычисляется произведение 1*1 и оно становится значением FACTORIAL(1). В выражение 2*FACTORIAL(1) вместо FACTORIAL(1) подставляется значение 1, вычисляется 2*1 и становится значением FACTORIAL(2). В выражение 3*FACTORIAL(2) вместо FACTORIAL(2) подставляется значение 2, вычисляется 3*2 и становится значением переменной FACTORIAL, которая возвращает в основную программу значение 3!.
Весь этот двухэтапный рекурсивный процесс реализуется в памяти ЭВМ с помощью организации в ней стека рекурсии. Дело в том, что для хранения значений переменной N (а значит, и переменной VALUE) отводится не одна ячейка, а стек с именем N. В этот стек последовательно заносятся значения 3, 2, 1, 0, причем значение 0 есть признак конца заполнения стека. Затем начинает работать цикл с телом FACTORIAL:= FACTORIAL * N, где значения N выбираются последовательно из стека в порядке 1,2,3. Исходным же значением переменной FACTORIAL является 1, как значение 0!.
Работа стека представлена на следующей схеме:
| Заполнение стека | Стек № | Вычисление |
| (углубление) | (разуглубление) | |
| FACTORIAL:=1 | 0 | FACTORIAL:=1 |
| FACTORIAL:=1*FACTORIAL(0) | 1 | FACTORIAL:=1*FACTORIAL |
| FACTORIAL:=2*FACTORIAL(1) | 2 | FACTORIAL:=2*FACTORIAL |
| FACTORIAL:=3*FACTORIAL(2) | 3 | FACTORIAL:=3*FACTORIAL |
В заключение покажем, что часто рекурсивные функции строятся гораздо проще, чем "обычные", хотя вполне понятно, что не всякая функция может быть переделана на рекурсивную. Сделаем это на примере уже построенной ранее функции POWER.
Данная функция явно носит рекурсивный характер, исходя из ее определения: Xn = 1, если n = 0;
Xn = (Xn-1)*X, если n > 1.
function POWER(FACTOR:real; EXPONENT:integer): REAL;
begin
if EXPONENT < 0
then POWER:=1/POWER(FACTOR,abs(EXPONENT))
else if EXPONENT > 0
then POWER:= FACTOR*POWER(FACTOR,EXPONENT-1)
ELSE POWER:=1
end;
ЗАМЕЧАНИЕ. Помимо рекурсивных функций в языке Паскаль можно определять по тому же принципу и рекурсивные процедуры. Подробно о них будет сказано в следующих разделах, а пока покажем, как рекурсивная функция может быть переделана в рекурсивную процедуру на примере вычисления факториала:
procedure FACTORIAL(VALUE:integer; var F: integer);
begin
iF VALUE=0 then F:=1
else begin FACTORIAL(VALUE-1,F);
F:=F*VALUE
end;
end;
Здесь уже, в отличие от функции FACTORIAL, для вычисления N! необходимо вызвать эту процедуру с помощью оператора процедуры FACTORIAL(N,FN), где FN - переменная для возвращения из процедуры значения N!.
Скалярный тип - простой тип данных. Скалярное данное неделимо. Массивы - это структурированные типы данных. Массив состоит из нескольких элементов. Ко всему массиву можно обращаться по его имени. Можно обращаться к его элементу, но для этого надо задать индекс (индексы). Массивы бывают одномерные и многомерные. Для объявления массива необходимо задать типы его индексов и компонент.
Тип компонент массива - это просто тип данных, ассоциированный с каждой компонентой массива. Тип компонент может быть любым REAL, INTEGER, CHAR, BOOLEAN, перечислимым, интервальным. В качестве компоненты массива может быть взят и тип массив.
Тип индекса должен быть одним из упорядоченных типов, т.е. любым скалярным типом, кроме REAL: INTEGER, CHAR, интервальный, перечислимый. Тип индекса определяет границы изменения индекса. Если сделана попытка использовать несуществующую компоненту, то возникает ошибка (ошибка неверного индекса).
Одномерный массив можно задать двумя способами:
а) с помощью служебного слова TYPE описывается тип массива, а затем с помощью VAR вводится переменная этого типа;
б) с помощью слова VAR сразу описывается переменная типа массив;
Например, объявление массива из 100 элементов типа REAL можно осуществить следующими двумя способами:
а) type R100 = array[1..100] of real;
var A: R100;
б) var A: array[1..100] of real.
Здесь задан массив с именем "А" и его элементы имеют имена: А[1],..., A[100]. Чаще всего для типа индекса используют интервальный тип на основе типов INTEGER и CHAR. Однако можно в качестве индексов брать перечислимый тип.
ПРИМЕР 1. Подсчет числа вхождений букв в текст определенной длины
program COUNTER;
var COUNT: array['a'..'z'] of integer;
CH: char; N: integer;
begin
for CH:= 'a' to 'z' do
COUNT [CH]:= 0; N:= 0;
repeat
read(CH); N:= N+1;
if (CH >= 'a') and (CH <= 'z') then
COUNT [CH]:= COUNT [CH]+1;
until CH = '.';
for CH:= 'a' to 'z' do
writeln(CH, COUNT [CH]:10, COUNT [CH]*100/N:10:2);
end.
ПОЯСНЕНИЕ. В этом примере тип индекса есть интервальный тип на базе типа CHAR, а тип компонент есть целое число. Таким образом, элементы массива - числа, а их индексы - буквы, т.е. число элементов массива равно 26 (число букв латинского алфавита). Рассмотрим теперь случай, когда тип индекса задан перечислимым типом, а компоненты массива представлены компонентами интервального типа на базе типа INTEGER.
ПРИМЕР 2. Присваивание переменной с именем месяца числа дней этого месяца
| DAY: | Значение элементов | ||||||||||
| 31 | 28 | 31 | 30 | 31 | 30 | 31 | 31 | 30 | 31 | 30 | 31 |
| Значение Индексов | |||||||||||
| JAN | FEB | MAR | APR | MAY | JUN | JUL | AUG | SEP | OKT | NOV | DEC |
program NUMBRDAY;
type MONAT = (JAN, FEB, MAR, APR, MAY, JUN, JUL, AUG,
SEP, OKT, NOV, DEC);
var DAY: array [MONAT] of 28..31; T: MONAT;
begin
for T:= JAN to DEC do
case T of
JAN, MAR, MAY, JUL, AUG, OKT, DEC: DAY[T]:= 31;
APR, JUN, SEP, NOV: DAY[T]:= 30;
FEB: DAY[T]:= 28;
end;
end.
Для определения позиции элемента в двумерном массиве необходимы два индекса. Любой двумерный массив есть матрица, а матрица есть таблица. Поэтому удобно описывать двумерные массивы путем указания границ изменения индексов (номеров) строк и столбцов.
Например, таблица символов M x N, где M - число строк и N - число столбцов, может быть описана:
var TAB: array[1..M, 1..N] of char.
| ОБЩАЯ ФОРМА ЗАПИСИ | ||||
| VAR <имя>:ARRAY [тип индекса строки, тип индекса столбца] | ||||
| OF <тип компонент>; | ||||
Однако, двумерный массив можно интерпретировать как вектор-столбец, каждый элемент которого в свою очередь является одномерным массивом (вектор - строка). Этот подход к определению двумерного массива влечет его описание с помощью двух строк, где первая содержит описание строки, а вторая - описание столбца:
type LINE = array[1..N] of char;
STOLB = array[1..M] of LINE;
var TAB: STOLB.
Здесь TAB[I] - переменнаятипа LINE, а TAB[I][J] - переменная
типа CHAR.
| ОБЩАЯ ФОРМА ЗАПИСИ | |||
| TYPE <тип строки>=ARRAY [тип индекса] OF <тип компонент>; | |||
| <тип столбца> = ARRAY[тип индекса] OF <тип строки>; | |||
| VAR <переменная массива>: <тип столбца(массива)>; | |||
Эти два вида определения массивов задают и два способа обращения к элементам массива: TAB[I,J] - в первом случае и TAB[I][J] - во втором.
Вполне очевидно, что сказанное выше для двумерного массива распространяется и на массивы большей размерности. Например, описание VAR CUBE: ARRAY[1..M, 1..N, 1..K] OF INTEGER определяет задание трехмерного массива целых чисел.
Обработка массивов включает в себя, как правило, следующие компоненты: ввод массива (с клавиатуры или с помощью датчика случайных чисел), вывод полученного массива на экран и собственно его обработка. Все эти компоненты рекомендуется оформлять в виде отдельных процедур. При этом надо учитывать следующий фактор: если процедуре (или функции) будет передаваться массив, то надо объявить в ней этот массив как параметр с атрибутом VAR даже в том случае, если значение массива внутри процедуры не изменяется. Это нужно для того, чтобы не тратить времени и памяти на размещение внутри процедуры копии массива. Заметим, что параметр обязательно должен относиться к типу, имеющему имя.
ПРИМЕР 3. Сумма элементов таблицы над верхней диагональю
program SUMMA;
const M =...; {числостроктаблицы}
N =...; {числостолбцовтаблицы}
type LINE = array[1..n] of integer;
TAB = array[1..m] of LINE;
var s,i,j:integer; MAS:TAB;
procedure VVODMASSIV(var MAS:TAB);
begin
¦ for i:=1 to M do
¦ for j:=1 to N do
¦ readln(MAS[i][j]);
end;
procedure VIVODMASSIV(var MAS:TAB);
begin
¦ for i:=1 to M do
¦ begin
¦ ¦ for j:=1 to N do
¦ ¦ write(MAS[i][j]:5,' '); writeln;
¦ end;
end;
procedure OBRABOTKA(MAS:TAB; var SUM:integer);
begin
¦ SUM:= 0;
¦ for i:=1 to M do
¦ for j:=1 to N do
¦ if j > i then SUM:= SUM+MAS[i][j];
end;
begin
¦ VVODMASSIV(MAS); writeln('исходныймассив');
¦ VIVODMASSIV(MAS); OBRABOTKA(MAS,s);writeln;
¦ writeln('сумма элементов = ',s);
end.
В Паскале, как и в других языках программирования, предусмотрена обработка текстов или строк. Для этой цели в языке существуют два типа данных: SHAR и STRING.