Занятие 7. Приём программирования рекурсия

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

Сущность рекурсии

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

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

Как нарисовать много флажков? Допустим, программа рисования флажка имеет такой вид:

сделай флажок
процедура флажок
… (команды рисования флажка) …
конец процедуры

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

сделай флажок
процедура флажок
… (команды рисования флажка) …
сделай флажок
конец процедуры

Здесь перед инструкцией конец процедуры процедуры флажок вставлена команда вызова процедуры флажок сделай флажок. Как будет выполняться такая программа?

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

Такой приём программирования, когда процедура вызывает сама себя из своего собственного тела, называется рекурсией. Вызов процедуры из её собственного тела называется рекурсивным вызовом.

Использование рекурсии

Предположим, что требуется написать программу для рисования горизонтальной линии через всё рабочее поле. Можно просто написать множество команд шаг — столько, сколько клеток в ширину на рабочем поле. Но, во-первых, рабочее поле может быть очень широким, и тогда программа станет слишком большой. А во-вторых, ширина рабочего поля может быть точно не известна, или программу требуется выполнять для рабочих полей разной ширины. В этих случаях с решением задачи возникнут трудности.

Однако теперь известно, что организовать многократное выполнение команды шаг можно с помощью рекурсии:


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