Файл: Рекурсивные и итерационные алгоритмы: Особенности и примеры использования (История развития языка программирования Pascal).pdf

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

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

Наиболее точно отражает дилемму выбора быть или не быть рекурсии цитата Ли Колдуэлла, опубликованная в Интернете:

«Циклы могут ускорить работу программы. Рекурсия может ускорить работу программиста. Выбирайте, что важнее в вашей ситуации!».

В следующем разделе курсовой работы рассмотрены основы программирования на языке Pascal ABC и реализация в нем алгоритмов с применением рекурсивного подхода.

2. РЕКУРСИВНЫЕ ПРОЦЕДУРЫ И ФУНКЦИИ

2.1 История развития языка программирования Pascal

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

Язык программирования высокого уровня Pascal был разработан в 1968-1971 годах швейцарским профессором Никлаусом Виртом (рисунок 4) с целью обучения студентов. Свой язык программирования Вирт назвал в честь яркого французского математика, физика, философа, изобретателя первого механического арифмометра Блеза Паскаля. [4]

Рисунок – Никлаус Вирт

Pascal быстро приобрел популярность среди разработчиков программного обеспечения благодаря своим очевидным достоинствам, к которым относят:

• простоту синтаксиса языка, прозрачность и структурированность программного кода;
• невысокие требования к аппаратным и системным ресурсам как со стороны компилятора языка Pascal, так и со стороны программ на этом языке;
• универсальность языка программирования Pascal, которая дает возможность разрабатывать на этом языке программы в рамках любой предметной области;
• благодаря строгой типизации языка программирования существенно минимизируется количество ошибок в кодах программ;
• поддержку различных современных технологий программирования (структурного программирования, программирования «сверху вниз», объектно-ориентированного программирования). [18]

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

1. Unextended Pascal - нерасширенный Pascal – это классический вариант языка, который был принят в 1983 году и фактически целиком совпадает с описанием языка Pascal по Никлаусу Вирту.
2. Extended Pascal - расширенный Pascal – стандарт языка с включенными в него расширениями, касающимися технологии модульного программирования (интерфейсная часть и реализация, отдельная компиляция модулей, импорт-экспорт подпрограмм). В расширенной версии также добавлены некоторые процедуры и функции – такие, как работа со строковыми переменными, прямой доступ файлов и другие.
3. Object Pascal – объектный Pascal – стандарт, утвержденный в 19993 году. Это язык программирования с наличием классов, характеризующихся свойствами и методами; поддерживающий наследование классов, полиморфизм (переопределение методов у потомков), а также иные атрибуты объектно-ориентированной методологии программирования. Язык программирования фирма Borland - разработчик среды Delphi начиная с версии Delphi 7.0 в официальной документации именует язык программирования Object Pascal как язык программирования Delphi.

Наиболее популярные формы реализации языка программирования Pascal представлены в таблице 1.

Таблица – Версии языка программирования Pascal

2.2 Основы программирования на языке программирования Pascal

Алфавит языка программирования высокого уровня Pascal составляют:

• строчные и заглавные латинские буквы;
• цифры десятичной системы счисления (0 – 9);
• символы кириллицы;
• зарезервированные символы (рисунок 5)

Рисунок – зарезервированные символы языка программирования Pascal

• зарезервированные сочетания символов (рисунок 6)

Рисунок – Зарезервированные сочетания символов языка Pascal

• ключевые (зарезервированные) слова.

Структура программы на языке программирования Pascal представлена на рисунке 7.

Рисунок – Структура программы на языке программирования Pascal

Идентификатором в языке программирования языка Pascal называется совокупность букв, знака подчеркивания, цифр, которая может начинаться только со знака подчеркивания или буквы, Наименование любого программного объекта (переменные, константы, типы, процедуры, функции, программа) должно по правилам языка являться идентификатором.

Информация, которую обрабатывает компьютер, хранится в его памяти. Отдельный информационный объект (число, символ, строка, таблица и другие) называется величиной. Величины в программировании, так же, как и математические величины, делятся на переменные и константы (постоянные). Pascal является строго типизированным языком программирования. Это означает, что любой объект до своего использования должен быть описан, то есть указано имя объекта и его тип. Иерархия типов данных языка программирования высокого уровня Pascal представлена на рисунке 8.

Рисунок – Иерархия типов языка программирования Pascal

2.3 Основные алгоритмические структуры в Pascal

Язык программирования высокого уровня Pascal поддерживает технологию структурного программирования, одним из постулатов которой является утверждение, что для реализации любого алгоритма достаточно трех базовых алгоритмических структур:

• следование;
• ветвление;
• повторение (цикл).

2.3.1 Линейный алгоритм

Линейная алгоритмическая структура (следование) представляет собой структуру, в которой пошагово описываются и выполняются те или иные команды. [14]

Линейный алгоритм представлен на рисунке 9.

Рисунок – Линейный алгоритм

2.3.2 Разветвляющийся алгоритм

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

Реализовать такую структуру можно с помощью условного оператора. Он имеет два вида записи (рисунок 10):

Рисунок – Неполная и полная формы оператора условного перехода

Пример блок-схемы реализации разветвляющегося алгоритма представлен на рисунке 11.

Рисунок - Разветвляющийся алгоритм

2.3.3 Циклический алгоритм

Простые циклы – это такая вычислительная схема разветвленной структуры, в которой одна ветвь операции сравнения является обратной связью на предыдущую часть алгоритма, т.е. идет назад. Таким образом, некоторая последовательность операций алгоритма будет выполняться многократно (в цикле), образуя тело цикла. Так можно многократно вычислять значения выражений по одним и тем же математическим зависимостям для различных значений входящих в них величин. Использование циклов позволяет сократить объем схемы алгоритма и длину программы. Циклы могут быть с заданным и с неизвестным числом повторений. Переменная, которая управляет циклом, называется параметром цикла. [20]

При построении любого цикла необходимо предусмотреть три момента:

1) организовать данные для первого цикла;

2) после выполнения цикла надо обновлять данные для очередного цикла;

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

В языке программирования Pascal реализованы три оператора цикла:

• цикл с параметрами for …to…do <тело цикла>;
• цикл с предусловием

while <условие> do <тело цикла>;

• цикл с постусловием

repeat <тело цикла> until <условие>.

Блок-схема реализации циклического алгоритма на примере цикла с параметрами представлена на рисунке 10.

Рисунок – Циклический алгоритм

2.4 Процедуры и функции в языке программирования Pascal

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

Подпрограмма - независимая часть программы, реализующая установленный алгоритм и разрешающая обращение к ней из разных частей основного модуля программы. Использование подпрограмм является основой одного из самых современных методов программирования - структурного программирования.[9]

В языке Паскаль существует два вида подпрограмм: процедура (ключевое слово - PROCEDURE) и функция (ключевое слово - FUNCTION).

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

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

Функция отличается от процедуры тем, что всегда возвращает в точку вызова одно значение. При этом функция, как и процедура, может содержать параметры – значения или быть без них.[10]

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

Синтаксис применения процедур и функций в Pascal имеет следующий формат.

Процедура

PROCEDURE <имя процедуры> (аргументы; VAR параметр-результат: тип);

begin

< тело процедуры>

end;

Функция

FUNCTION <имя функции> (аргументы): тип;

begin

< тело функции>

end;

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

2.5 Реализация рекурсии в языке программирования Pascal

Ниже рассмотрены как классические примеры использования рекурсии – реализация операции возведения в степень и вычисление факториала числа, так и менее распространенные программные этюды с использованием рекурсии на языке программирования PascalABC.

2.5.1 Возведение в степень

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