Прямая и косвенная рекурсия. Особенности использования.

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

Косвенная рекурсия. Функция обращается к себе путем вызова другой подпрограммы, которая и содержит обращение к функции. (Procedure A (K:Byte); Begin B (K); end; Procedure B (N:byte); Begin A (N); End;). Программа работать не будет, т. к. она не может вызвать из А процедуру В, т..к для этого описание процедуры В должно быть расположено до вызова. В данной ситуации в Паскале существует т. называемое опережающее описание, его суть: до вызываемой процедуры А дается только заголовок вызываемой процедуры В. А вместо тела, вызываемой процедуры В пишется ключевое слово FORWARD. В этом случае описание вызываемой процедуры начинается с заголовка процедуры, в котором нет формальных параметров. (Procedure B (N:byte); Forward; procedure a (k:byte); begin B (K); end; Procedure B; Begin A (N); End;). Рекомендуется использовать директиву {$ S+}. Она включается для проверки стека (памяти, где хранится состояние вызывающей программы) и если будет переполнение стека, то программа будет остановлена и выдано сообщение об ошибке. В начале каждой процедуры или функции вызываемого рекурсивно разместить строку: if Keypressed then HALF, тогда при зависании программы надо нажать любую клавишу.

 

Структура языка Паскаль. Структура программ на языке Паскаль.

Алгоритмический язык – это система правил для описания процесс обработки данных. Он включает алфавит, из символов которого формируются слова, выражения и операторы (предложения). Алфавит – Это набор допустимых символов языка. Слова (идентификаторы, константы) формируются из символов по определенным правилам. Выражения – это группа слов, имеющих определенный смысл. Операторы - это предложения для описания некоторого действия в процессе обработки данных. Из операторов формируются программы. Алгоритмический язык должен иметь формальные правила определения всех конструкций, допустимых в языке, и правила их толкования. Систему правил формирования множества конструкций языка (слов, выражений, операторов) представляет синтаксис языка. Систему правил истолкования смысла конструкций языка человеком и соответствующую им реализацию этих правил транслятором определяет семантика. Семантика может быть задана формально, с помощью металингвистических формул, и неформально, словесным описанием. Семантика определяет назначение конструкции, ее особенности, ограничения и т.п. Структура различных языков программирования однотипна. Они должны иметь средства для: определения свойств объектов программы (ее данных); определения обработки, т.е. получения новых значений объектов; организации процесса обработки данных; ввода/вывода данных, т. е. Обмена данными между ОП и внешними устройствами (магнитными дисками, портами, принтером); формирования и использования модулей (программ, процедур и функций) и библиотек модулей (системных и пользовательских, разработанных программистом).

Структура языка Паскаль

В текстах программ допускаются комментарии и пробелы. Комментарий – это текст, поясняющий программу и не влияющий на процесс ее выполнения. Комментарии ограничиваются символами { и} или (* и *). Программа на языке Паскаль состоит из заголовка программы и блока (тела программы). Заголовок программы или подпрограммы – это один из операторов: PROGRAM – для программы; PROCEDURE – для процедуры; FUNCTION – для функции. Процедуры и функции могут иметь ряд уровней вложенности, т.е. могут быть вложены в другие процедуры и функции. Форма оператора заголовка программы: Program имя_программы; Пример структуры программы:

Program PR; - заголовок программы

Объявление типов, констант, меток и переменных;

Блок программы и подпрограммы на языке Паскаль состоит из двух частей: 1) декларативной – описания (объявления) данных программы и текстов подпрограмм (разделы описаний); 2) выполнимой – описания действий, которые надо выполнить над данными (раздел операторов). Блок включает все, кроме заголовка программы или подпрограммы. В общем случае может состоять из шести разделов различных типов. Все они, кроме раздела операторов, необязательны. Каждый раздел описаний начинается ключевым словом: Label – для определения меток программы; Const – для определения констант Type – для определения типов данных, Var – для определения переменных, Procedure и Function – для определения процедур и функций, Begin – определяет начало раздела операторов программы. Оператор Program должен быть первым в программе, раздел операторов программы – последним. А между ними может быть сколько угодно разделов описаний в любом порядке. Типы и константы могут использоваться в последующих описаниях типов и переменных и программ. Последовательность разделов описания объектов (Label, Const, Type,Var и др.) программы может быть произвольной. В случае необходимости типы разделов могут повторяться. Умолчаний в Паскале нет. Все, что используется в программе: константы, переменные, метки, - должно быть обязательно явно. Каждый объект программы должен быть описан и только один раз для данной области действия. Объекты программы имеют областью их действия блок, в котором они объявлены, и все вложенные в него блоки, процедуры и функции, в которых они не переобъявлены. Поэтому одни и те же идентификаторы можно использовать в различных подпрограммах (процедурах и функциях) программы в разных смыслах.