Занятие 9. Алгоритмическая конструкция цикл.

(поделиться сведениями)

Недостатки рекурсии

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

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

В реализации среды ГРИС Букашка запоминается только точка возврата из процедуры, потому что контекст представлен состоянием рабочего поля и не требует восстановления после возврата из процедуры. Память, которая задействуется под хранение точки возврата, освобождается только после завершения выполнения процедуры командой конец процедуры. Если же из тела процедуры вызывается другая (или та же самая) процедура, то дополнительно запоминается ещё одна точка возврата. Рекурсивные вызовы могут потребовать довольно много памяти для хранения этих сведений (рис. 9.1).

Рекурсивные вызовы и возвраты из процедуры
Рис. 9.1.Использование памяти для хранения точек возврата при рекурсивных вызовах.

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

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

В ГРИС Букашка размер стека равен 100, чего хватает для выполнения не более 100 рекурсивных вызовов. Но для 101-го рекурсивного вызова сохранить точку возврата уже некуда, и происходит ошибка выполнения программы. На практике стек используется для реализации всех алгоритмических конструкций, кроме следования, поэтому реальное максимальное количество рекурсивных вызовов может быть ещё меньше.

Цикл

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

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

В зависимости от того, перед выполнением команд тела цикла или после их выполнения проверяется условие выполнения цикла, различают два вида циклов: цикл ПОКА (цикл с предусловием) и цикл ДО (цикл с постусловием). Различия между этими циклами наглядно демонстрирует графическая схема (рис. 9.2).

Циклы с пред- и постусловием
Рис. 9.2. Цикл ПОКА (слева) и цикл ДО (справа)

В цикле ПОКА условие проверяется перед тем, как выполнять тело цикла. Поэтому, если условие сразу будет нарушено, команды тела цикла не будут выполнены ни разу, и управление будет передано команде, следующей после цикла. В цикле ДО условие проверяется после выполнения команд тела цикла, поэтому в нём тело цикла будет выполнено как минимум один раз.

В СКИ ГРИС Букашка имеются команды только для организцаии циклов ПОКА. Они записываются так:

пока впереди край, повторять
…
(команды тела цикла)
…
конец цикла

и

пока впереди не край, повторять
…
(команды тела цикла)
…
конец цикла

Условие выполнения цикла заключается в оценке пространства перед исполнителем — находится перед ним граница рабочего поля или свободная клетка?

Как и в случае с командами ветвления и организации процедур, для быстрого ввода команд цикла можно использовать пункт меню F4…. Для указания позиции начала цикла и условия его выполнения надо в подменю выбрать пункт F6пока…, после чего — F1…впереди край или F2…впереди не край. Для указания конца тела цикла в подменю надо выбрать пункты F9конец... и F2…цикла.

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

С помощью команд цикла можно составить программу рисования горизонтальной линии без использования рекурсии: