Использование рекурсивных процедур

Вернемся к вопросу об использовании процедур при составлении программ управления исполнителями алгоритмов (см. § 5 нашего учебника). Но это будет особый вид процедур, которые называются рекурсивными процедурами.

Не все учебные исполнители алгоритмов допускают использование рекурсивных процедур (рекурсии). Такая возможность имеется в учебной программе «Стрелочка», реализующей один из вариантов графического исполнителя алгоритмов (ГРИС)* (*Единая коллекция цифровых образовательных ресурсов (ЕК ЦОР): http: //school-collection. edu. ru /). При программировании некоторых задач рекурсия может служить альтернативой циклу.

Приведем пример использования в программе для ГРИС «Стрелочка» рекурсивной процедуры вместо цикла.

Пусть начальное положения «Стрелочки» — произвольная точка в первой строке рабочего поля, направление «вправо» (рис. 1.16). Требуется построить линию, идущую из этой точки до правой границы области.

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

алгоритмПУТЬ_1_0

Дано: исполнитель в точке А

Надо: воспроизвести образец

Нач

покавпереди НЕ стена

нц

Шаг

кц

Кон

А теперь воспользуемся рекурсией, для чего опишем процедуру ЛИНИЯ_1.

алгоритм ПУТЬ_1_1

Дано: Исполнитель в точке А

Надо: Воспроизвести образец

Нач

делай ЛИНИЯ1

Кон

процедура ЛИНИЯ1

Шаг

делайЛИНИЯ1

Конец процедуры

В теле этой процедуры присутствует команда обращения к самой себе: делай ЛИНИЯ1.

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

Трассировка алгоритма

Команда	Пояснение
начало делай ЛИНИЯ1 шаг делай ЛИНИЯ1 шаг делай ЛИНИЯ1	Вызов процедуры в основной программе     1-й рекурсивный вызов процедуры   2-й рекурсивный вызов процедуры   Далее возникнет ситуация НЕ МОГУ, так как исполнитель дошел до стены. Выполнение программы завершится аварийно

В этом случае завершение исполнения алгоритма произойдет аварийным образом (ситуация НЕ МОГУ).

Дело в том, что в данном алгоритме мы имеем дело с бесконечно повторяющимся рекурсивным обращением к процедуре, что недопустимо. Количество обращений процедуры к самой себе при ее исполнении называется глубиной рекурсии. Глубина рекурсии должна быть конечной. Для исполнителя «Стрелочка» естественным ограничением количества обращений процедуры самой к себе может служить только достижение стены. Следовательно, рекурсивный вызов в процедуре надо поместить в команду ветвления, проверяющую условие достижения стены. Вот новый вариант алгоритма.

алгоритм ПУТЬ_1_2

Дано: Исполнитель в точке А

Надо: Воспроизвести образец

Нач

делайЛИНИЯ 2

Кон

процедураЛИНИЯ 2

если впереди НЕ стена

то

Шаг

делай ЛИНИЯ 2

Все

Конец процедуры

Трассировка этого алгоритма представлена в следующей таблице:

Трассировка алгоритма

Команда	Пояснение
начало делайЛИНИЯ 2 если впереди НЕ стена то шаг делай ЛИНИЯ 2 если впереди НЕ стена то шаг делай ЛИНИЯ 2 если впереди НЕ стена все все все конец	Первый вызов процедуры Да   Рекурсивный вызов Да     Рекурсивный вызов Нет     Программа выполнилась, рисунок получен

Поскольку в описании алгоритма присутствует «точка остановки» (условие окончания исполнения алгоритма), исполнитель «Стрелочка», дойдя до стены, остановится.

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

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

алгоритм ПУТЬ_2

Дано: Исполнитель в точке А

Надо: Воспроизвести образец

Нач

делай ЛИНИЯ_3

Кон

процедура ЛИНИЯ_3

если впереди НЕ стена

то

Шаг

делай ЛИНИЯ_3

Прыжок

Иначе

Поворот

Поворот

Все

Конец процедуры

Трассировка алгоритма ПУТЬ_2 для исходного положения исполнителя за два шага до стенки показана в следующей таблице.

Трассировка алгоритма

Команда	Пояснение
начало делай ЛИНИЯ З если впереди НЕ стена то шаг делай ЛИНИЯ 3 если впереди НЕ стена то шаг делай ЛИНИЯ 3 если впереди НЕ стена иначе поворот поворот все прыжок все прыжок все конец	Первый вызов процедуры Да     Рекурсивный вызов Да     Рекурсивный вызов Нет     Разворот на 180 градусов   Возврат в 2 прыжка в исходную точку     Программа выполнилась

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

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

Коротко о главном

Рекурсивной называется процедура, в которой имеется обращение к самой себе.

Использование рекурсии может быть эквивалентом использованию цикла.

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

Вопросы и задания

1. Что такое рекурсивная процедура?

2. В каком порядке происходит выход из последовательности рекурсивных обращений?

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

алгоритмФИГУРА-1

Дано: Исполнитель в точке А

Надо: Воспроизвести образец

Нач

делай ЛИНИЯ

Поворот

Поворот

Поворот

Шаг

Шаг

Кон

процедураЛИНИЯ

если впереди НЕ стена

то

Шаг

делай ЛИНИЯ

Шаг

Иначе

Поворот

Поворот

Поворот

Шаг

Шаг

Поворот

Поворот

Поворот

Все

Конец процедуры

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

§8

Что такое программирование

Основные темы параграфа:

■кто такие программисты;

■что такое язык программирования;

■ что такое система программирования.

Кто такие программисты

Теперь вам предстоит ближе познакомиться еще с одним разделом информатики, который называется «Программирование».

Специалисты, профессионально занимающиеся программированием, называются программистами. В первые годы существования ЭВМ для использования компьютера в любой области нужно было уметь программировать. В 1970-1980-х годах начинает развиваться прикладное программное обеспечение. Бурное распространение прикладного ПО произошло с появлением персональных компьютеров. Стало совсем не обязательным уметь программировать для того, чтобы воспользоваться компьютером. Люди, работающие на компьютерах, разделились на пользователей и программистов. В настоящее время пользователей гораздо больше, чем программистов.

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

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

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