Цикл while-do цикл repeat-until

{Подготовка} {Подготовка}

While L do repeat
begin {тело цикла}

{тело цикла} until L;
end;

здесь L -логическое выражение, которое при значении True явля­ется условием продолжения выполнения while-do или условием окончания выполнения repeat-until. Подготовка и тело цикла явля­ются цепочками функциональных узлов.

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

Очень часто количество итераций цикла известно заранее: это либо константа, известная при написании программы, либо значе­ние, вычисляемое перед началом цикла. Цикл со счетчиком можно запрограммировать следующим образом:

for <параметр_цикла>:= <нач_знач>

to <кон знач> do <оператор>;

здесь for, to, do — зарезервированные слова; <параметр _цикла> — переменная любого перечисляемого типа.

Цикл выполняется для каждого из значений от <нач_знач>

и до <кон_знач>.

ОПЕРАТОРЫ ПЕРЕХОДА

Оператор безусловного перехода имеет следующий вид: goto, здесь goto — зарезервированное слово: <метка> — метка.

Метка - это произвольный идентификатор, позволяющий име­новать некоторый оператор программы и таким образом ссылаться на него.

Можно теоретически показать, что достаточно if- и while-операторов, чтобы записать любую необходимую управляющую структуру. Однако есть несколько вполне определенных ситуаций, где лучше использовать оператор goto.

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

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

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

В современных языках Object Pascal, Ada, C++ и Eiffel есть спе­циальные языковые конструкции, так называемые исключения, ко­торые непосредственно решают и эту проблему.

ПОДПРОГРАММЫ. ПРОЦЕДУРЫ И ФУНКЦИИ

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

Подпрограмма -- некоторая последовательность инструкций, которая может повторяться в нескольких местах программы.

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

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

Описание процедуры состоит из заголовка и тела. Заголовок процедуры имеет вид:

procedure <имя> [ (<сп.ф.п.>) ];

здесь <имя> имя процедуры (правильный идентификатор); <сп. ф. п. > - список формальных параметров.

Список формальных параметров необязателен и может отсутст­вовать. Если же он есть, то в нем должны быть перечислены имена формальных параметров и их типы, например procedure MyProc (a: Real; b: Integer; с: Char);

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

function <имя> [(<сп.ф.п.>)]: <тип>;

здесь <тип> — тип возвращаемого функцией результата. Заголовок функции может иметь следующий вид:

function MyFunc (a, b: Real): Real;

Операторы тела подпрограммы рассматривают список фор­мальных параметров как своеобразное расширение раздела описа­ний: все переменные из этого списка могут использоваться в лю­бых выражениях внутри подпрограммы. Так осуществляется на­стройка алгоритма подпрограммы на конкретную задачу. Работа с процедурами и функциями отличаются в следующем:

1) в заголовке функции помимо описания формальных пара­метров обязательно указывается тип возвращаемого ею результата;

2) для возврата функцией значения в точку вызова среди ее операторов должен быть хотя бы один, в котором имени функции или переменной Result присваивается значение результата;

3) вызов процедуры выполняется отдельным оператором;

4) вызов функции может выполняться там, где допускается ста­вить выражение, например, в правой части оператора присваивания.

ПЕРЕДАЧА ПАРАМЕТРОВ

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

Механизм замены формальных параметров на фактические по­зволяет нужным образом настроить алгоритм, реализованный в подпрограмме. Компилятор обычно следит за тем, чтобы количе­ство и тип формальных параметров строго соответствовали коли­честву и типам фактических параметров в момент обращения к подпрограмме.

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

параметры-значения;

параметры-переменные;

параметры-константы.

Например, procedure MyProc (A: Real; var В: Real; const С: String);

здесь А - параметр-значение, в - параметр-переменная, С - пара­метр-константа.

Способ определения формального параметра очень важен для вызывающей программы. Если формальный параметр объявлен как параметр-значение или параметр-константа, то при вызове ему мо­жет соответствовать произвольное выражение. Если формальный параметр объявлен как параметр-переменная, то при вызове под­программы ему должен соответствовать фактический параметр в виде переменной нужного типа.

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

Если параметр определен как параметр-значение, то перед вы­зовом подпрограммы это значение вычисляется, полученный ре­зультат копируется во временную память и передается подпро­грамме. Любые возможные изменения в подпрограмме параметра-значения никак не воспринимаются вызывающей программой, так как в этом случае изменяется копия фактического параметра.

Если параметр определен как параметр-переменная, то при вы­зове подпрограммы передается сама переменная, а не ее копия (фактически в этом случае подпрограмме передается адрес пере­менной). Изменение параметра-переменной приводит к изменению самого фактического параметра в вызывающей программе.

В случае параметра-константы в подпрограмму также передает­ся адрес области памяти, в которой располагается переменная или вы­численное значение. Однако компилятор блокирует любые присваи­вания параметру-константе нового значения в теле подпрограммы.

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

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

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

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

Нетипизированные параметры. Одним из свойств языка Object Pascal является возможность использования нетипи­зированных параметров.

Параметр считается нетипизированным, если тип формального параметра-переменной в заголовке подпрограммы не указан, при этом соответствующий ему фактический параметр может быть пе­ременной любого типа. Нетипизированными могут быть только параметры-переменные: procedure MyProc(var aParametr);

Нетипизированные параметры обычно используются в случае, когда тип данных несуществен. Такие ситуации чаще всего возни­кают при разного рода копированиях одной области памяти в дру­гую, например, с помощью процедур BlockRead, BlockWrite, Move-Memory и т. п.

Процедурные типы. Основное назначение процедурных типов — дать программисту гибкие средства передачи функций и процедур в качестве фактических параметров обращения к дру­гим процедурам и функциям. Для объявления процедурного типа используется заголовок процедуры (функции), в котором опускает­ся ее имя, например:

type

Prod = procedure (a, b, с: Real; var d: Real);

РгосЗ == procedure;

Fund = function: String;

Func2 = function (var s: String): Real;

В программе могут быть объявлены переменные процедурных типов, например:

var

p1: Proc1;

fl, f 2: Func2;

ар: array [1.. N] of Prod;

Переменным процедурных типов допускается присваивать в ка­честве значений имена соответствующих подпрограмм. После та­кого присваивания имя переменной становится синонимом имени подпрограммы.

2.7. РЕКУРСИЯ

Содержание и мощность рекурсивного определения, а также его главное назначение, состоит в том, что оно позволяет с помощью конечного выражения определить бесконечное множе­ство объектов. Аналогично, с помощью конечного рекурсивного алгоритма можно определить бесконечное вычисление, причем ал­горитм не будет содержать повторений фрагментов текста.

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

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

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

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

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

В общем случае любая рекурсивная процедура Rec включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова.

Безусловные рекурсивные процедуры приводят к бесконечным процессам, и на эту проблему нужно обратить особое внимание, так как практическое использование процедур с бесконечным са­мовызовом невозможно.

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

Если условие истинно, то рекурсивный спуск продолжается. Когда оно становится ложным, то спуск заканчивается и начинает­ся поочередный рекурсивный возврат из всех вызванных на дан­ный момент копий рекурсивной процедуры. Структура рекурсивной процедуры может принимать три раз­ных формы:

1) форма с выполнением действий до рекурсивного вызова (на
рекурсивном спуске);

procedure Rec; begin

S;

if условие then Rec; end;

2) форма с выполнением действий после рекурсивного вызова
(на рекурсивном возврате);

procedure Rec; begin

if условие then Rec;

S; end;

3) форма с выполнением действий как до, так и после рекур­сивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).

procedure Rec; begin

S1;

if условие then Rec; S2; end;

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