Понятие рекурсии. Рекурсивные процедуры и функции, их применение, достоинства и недостатки

Рекурсия - это способ организации вычислительного процесса, при котором процедура или функция в процессе выполнения входящих в ее состав операторов обращается сама к себе непосредственно, либо через другие процедуры и функции.

Рекурсия может быть прямой или косвенной. При прямой рекурсии оператор вызова подпрограммы содержится непосредственно в ее исполняемой части. Любую рекурсивную процедуру (функцию) можно сделать не рекурсивной. Рекурсивное описание обычно короче и нагляднее, но требует больших затрат машинного времени (за счет повторных обращений) и памяти машины (за счет дублирования переменных). Рекурсивная подпрограмма однократно вызывается извне. Условие полного окончания работы рекурсивной процедуры или функции должно находиться в ней самой.

Рассмотрим пример. Вычислить значение F=M! Рекурсивное определение значение факториала можно записать следующим образом: при М=1 F=1; при М> 1 F= M!= M*(M-1)!, т.е. М! определяется через (М-1)!

a) Рекурсивная функция

PROGRAM MAIN;

VAR M: INTEGER;

F:REAL;

FUNCTION FACT (N:INTEGER): REAL;

BEGIN

IF N=1 THEN

FACT:=1

ELSE

FACT:= N* FACT(N-1);

END;

BEGIN

READLN(M);

F:= FACT (M);

WRITELN (' M!=', F);

END.

b) Рекурсивная процедура

PROGRAM MAIN;

VAR M: INTEGER;

F:REAL;

PROCEDURE FACT(N:INTEGER; VAR F: REAL);

VAR Q: REAL;

BEGIN

IF N=1 THEN Q:=1

ELSE FACT(N-1,Q);

F:=N*Q;

END;

BEGIN

READLN(M);

FACT (M, F);

WRITELN (' M!=', F);

END.

B варианте а) при м=4 выполняются следующие действия: FACT:=4*FACT(3); FACT:=3*FACT(2); FACT:=2*FACT(1); FACT(1):=1.

При входе в функцию в первый раз отводится память под локальную переменную, соответствующую параметру-значению; ей присваивается значение фактического параметра (М). При каждом новом обращении строятся новые локальные переменные. Так как FACT(1)=1, то выполнение функции заканчивается. После этого выполняются действия: FACT(1):=1; FACT:=2*FACT(1); FACT(2):=2; FACT:=3*FACT(2); FACT(3):=3*2=6; FACT:=4*FACT(3); т.е. FACT=24.

Область действия (видимости) имен. Глобальные и локальные переменные. Достоинства и недостатки использования глобальных переменных и параметров при обмене информацией между программами. Рекомендации по применению

Любая подпрограмма представляет собой блок со своей областью описаний. Она может содержать внутри этого блока описания других процедур и функций, а также обращения к ним. Объекты, описанные внутри какого-либо блока, являются по отношению к нему локальными и не доступны внешним блокам. На них можно ссылаться тольковнутри блока, в котором они описаны. Под объектами понимаются имена констант, типов, переменных, процедур, функций. Объекты, описанные во внешних блоках и не описанные во внутренних, являются глобальными по отношению к внутренним и доступны как во внешнихблоках, так и во внутренних. При совпадении имен глобальных и локальных переменных, локальные переменные отменяют действия глобальных в пределах области своего действия.

Если подпрограмма имеет параметры, то идентификаторы из списка формальных параметров являются локальными для этой процедуры (функции) и глобальными для каждой подпрограммы в ней (если таковые имеются).

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

Достоинства и недостатки глобальных переменных:

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

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

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

 

10. Запись как тип данных. Работа с записями: описание записи, оператор присоединения, запись с вариантами. Использование записей

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

В общем виде описание типа для записи можно представить:

TYPE <идентификатор типа>= RECORD

<идентификатор 11>[,< идентификатор 12>,…]: <тип 1>;

< идентификатор 21>[,< идентификатор 22>,…]: <тип 2>;

...

END;

Например,

TYPE TA= RECORD

P1: REAL;

P2: CHAR;

P3: BYTE

END;

VAR A: ARRAY[1..10] OF TA;

Здесь описан одномерный массив, каждый элемент которого представляет собой запись, имеющую структуру типа TA.

Запись может объявляться и непосредственно в разделе описания переменных.

VAR C: RECORD

P1: REAL;

P2: CHAR;

P3: BYTE

END;

При обращении к компонентам записи используются составные имена. Для сокращения имен и повышения удобства работы с записями применяется оператор присоединения WITH.

WITH <идентификатор переменной типа RECORD> DO < оператор >;

Тогда в операторе при ссылке на компоненты записи имя переменной можно опускать.

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

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

TYPE <идентификатор типа >= RECORD

<идентификатор поля 1>:<тип 1>;

<идентификатор поля 2>:<тип 2>;

...

CASE <селектор>:<тип селектора> OF

<метка варианта 1>:(<поле варианта 11>:<тип 11> [;<поле вар-та

12>:<тип 12>;<поле варианта 13>:<тип 13>;...]);

END;

Метки варианта должны иметь такой же тип, как у селектора.

Если какой-либо метке варианта не соответствуют поля, то записываются пустые круглые скобки.

Пример:

Пусть требуется описать запись следующей структуры. В каждой записи имеются поля, содержащие табельный номер и фамилию. В зависимости от того, кому принадлежит запись, состав остальных полей может быть разным:

- для студентов поля: номер группы и специальность;

- для преподавателей: институт, кафедра, стаж работы;

- для сотрудников дополнительных полей нет.

Описание соответствующей записи структуры данных:

TYPE TZ=RECORD

TN:BYTE;

FIO:STRING;

CASE N:CHAR OF

‘P’: (IN:BYTE; KAF:STRING; ST:BYTE);

‘S’: (NG:BYTE; SP:INTEGER);

‘A’: ()

END;

VAR Z:TZ;

 

Файлы в Паскале. Понятие физического и логического файла, соотношение между ними. Типы файлов и их описание, стандартные процедуры и функции для работы с файлами. Общие характеристики методов доступа к файлам

При обработке на компьютере информация может храниться на внешних носителях в виде файлов.

Файл на носителе – это поименованная совокупность логически связанных между собой данных (записей), имеющая определенную организацию и общее назначение.

Физическая запись – это совокупность данных, передаваемых в прямом или обратном направлении при одном обращении к внешнему носителю (т.е. минимальная единица обмена данными между внешней и оперативной памятью. С физическими записями - блоками работает операционная система). Физическая запись состоит из логических записей.

Логическая запись – единица данных, используемая в операторах чтения и записи файлов, порция информации, обрабатываемая в программе «за один раз». Логические записи объединяются в физическую запись для уменьшения числа обращений к внешнему устройству.

Для обращения к записям файла на внешнем носителе используется понятие логического файла.

Логический файл или файл в программе – это совокупность данных, состоящая из логических записей, объединенных общим назначением.

− В данный момент времени возможен доступ через данный логический файл только к одному физическому файлу.

− Число записей в файле произвольно.

− В каждый момент времени доступна только одна запись.

− Длиной файла называют количество записанных компонентов. Файл, не содержащий записей, называется пустым.

Стандартные средства обеспечения взаимодействия между логическим и физическим файлом:

1) установление связи между физическим и логическим файлами ASSIGN ( …), где указывается имя файла в программе и имя файла на внешнем носителе (без контроля существования файла);

2) обеспечение физической возможности обмена информацией между файлами, открытие файла для чтения информации из него RESET (…) или для записи в него REWRITE (…). При этом осуществляется контроль наличия физического файла;

3) прекращение, отмена возможности физического обмена информацией между файлами, закрытие файла CLOSE (…). Связь между файлами при этом не разрывается (т.е. ASSIGN действует).

При работе с файлами необходимо придерживаться следующих общих правил:

- каждый файл в программе (переменная файлового типа) должен быть объявлен в разделе VAR. Не допускается использование таких переменных в выражениях и операторах присваивания. Тип компонентов файла может быть любым, кроме файлового.

- каждый файл в программе должен быть закреплен за конкретным файлом на носителе процедурой ASSIGN;

- открытие существующего файла для чтения, корректировки или дозаписи производится процедурой RESET, открытие создаваемого файла для записи – процедурой REWRITE;

- по окончании работы с файлом он должен быть закрыт процедурой CLOSE.

Процедуры и функции для работы с файлами.

ASSIGN (имя_файла_в_программе, имя_файла_на_носителе) – процедура устанавливает связь между файловой переменной ( имя_файла_в_программе) и файлом на носителе. Здесь:

имя_файла_в_программе - это файловая переменная, т.е. идентификатор, объявленный в программе как переменная файлового типа.

имя_файла_на_носителе – текстовое выражение, содержащее имя файла или имя логического устройства. Перед именем файла на носителе может быть указан полный путь к файлу – имя диска, имена каталогов вышестоящих уровней, имя текущего каталога. Это единственное место в программе, где используется имя физического файла на носителе. Во всех остальных местах используется имя логического файла, имя файла в программе.

RESET (имя_файла_в_программе) – процедура открытия существующего файла

− для чтения при последовательном доступе и

− для чтения и записи при прямом доступе.

Указатель файла при этом устанавливается на первую запись (с 0 номером). Если файл с таким именем не существует, то происходит аварийное завершение программы.

REWRITE (имя_файла_в_программе) – процедура открытия создаваемого файла для записи. Если файл с таким именем не существовал, то он создается и начинается заполнение файла. Если файл с таким именем уже существовал, то он стирается, и заполнение файла начинается заново. Указатель файла устанавливается на первую запись (запись – она же компонент файла).

READ (имя_файла_в_программе, имя_переменной) – процедура чтения очередного компонента файла в переменную, тип которой должен совпадать с типом компонентов файла.

READLN (имя_файла_в_программе, имя_переменной) применяется для чтения записей из текстового файла.

WRITE (имя_файла_в_программе, имя_переменной

[, имя_переменной …]);

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

WRITELN (имя_файла_в_программе, имя_переменной) – применяется для записи компонента в текстовый файл.

SEEK (имя_файла_в_программе, номер_компонента ) – процедура установки текущего указателя для чтения или записи требуемого компонента файла.

CLOSE (имя_файла_в_программе) – процедура закрытия файла. Обязательно должна использоваться после окончания работы с файлом, в особенности после создания файла, иначе может произойти потеря данных, находящихся в последнем буфере. В одной программе файл может быть открыт и закрыт несколько раз с разными назначениями.

FILEPOS (имя_файла_в_программе) – функция определения номера текущей записи файла.

FILESIZE (имя_файла_в_программе) – функция определения общего количества записей файла.

EOF (имя_файла_в_программе) – функция определения признака конца файла (End Of File). Получает значение TRUE при чтении последней записи файла.

EOLN (имя_файла_в_программе) – функция обнаружения конца строки в текстовом файле (End Of Line). Имеет значение TRUE, если найден конец строки.

IORESULT – функция возврата условного признака последней операции ввода-вывода. Если операция завершилась успешно, функция возвращает нуль. Функция становится доступной только при отключенном автоконтроле ошибок ввода-вывода. Директива компилятора {$I-} отключает, а {$I+} – включает автоконтроль ошибок. Если автоконтроль отключен и операция ввода-вывода привела к возникновению ошибки, все последующие обращения к вводу-выводу блокируются, пока не будет вызвана функция IORESULT. Функция, как правило, применяется для контроля существования файла, с которым предстоит работать.

ERASE (имя_файла_в_программе) – процедура уничтожения файла. Открытый файл прежде должен быть закрыт (используется модуль DOS).

RENAME (старое _ имя_файла_на_носителе, новое_имя_файла_на_носителе) – процедура для переименования файла. Используется после закрытия файла (используется модуль DOS).

В системе программирования Паскаль различаются 3 вида файлов:

· файлы с типом записей (типизированные файлы);

Type

Rec = record

Inf1: integer;

Inf2: string [20];

End;

Var

Zap: rec; { компонент файла – место в ОП для одной записи файла }

F1: file of rec; { файл со структурой компонента вида REC }

· текстовые файлы со строками неопределенной длины;

VAR F2: TEXT;

· файлы без типа для передачи данных блоками записей.

VAR F3: FILE;