Рисующие руки. Рисунок М.Эшера
Рисующие руки. Рисунок М.Эшера
Разрабатывая программы на языке программирования ЛОГО, мы пользовались методом выделения составных частей в задаче.
В итоге наши программы складывались, как из кубиков, из отдельных модулей - процедур, которые содержат обращения друг к другу.
Возникает вопрос - может ли процедура содержать обращение к самой себе и, если ответ "да", что из этого может получиться?
Действительно, не все языки программирования поддерживают эту возможность, но в Лого такие обращения разрешены и порою
приводят к очень интересным результатам.
Называется это рекурсией.
Рекурсия - это такая организация алгоритма, при которой процедура обращается к самой себе. Сама процедура называется рекурсивной.
В жизни вам не раз приходилось сталкиваться с рекурсией. Вспомните хотя бы стихотворение "У попа была собака" или то, как, сидя в поезде, вы ловили свое отражение в зеркале, которое отражалось в зеркале напротив, которое отражалось в зеркале напротив...
Итак, отправляемся в мир волшебной рекурсии.
Начнем изучение рекурсии с простой процедуры, рисующей спираль. Спиралевидные формы - нередко встречаются в природе, они прекрасны и совершенны. Их можно встретить в растениях, без труда найти среди морских и речных раковин, да и сама наша галактика имеет форму спирали.
Опишем нашу процедуру следующим образом:
TO SPIRAL :A FD :A RT 90 SPIRAL :A-5 END
Выполним вместе с Черепашкой команду SPIRAL 20 и посмотрим, как она реализуется в компьютере.
| Первый вызов: | SPIRAL 20 | |
| Вторая строка: | FD :A | Черепашка продвигается вперед на 20 шагов |
| Третья строка: | RT 90 | Черепашка поворачивается направо на 90 градусов |
| Четвертая строка: | SPIRAL :A-5 | Вызывает процедуру SPIRAL и передает ей значение параметра 20-5=15 |
|
Чтобы выполнить этот вызов, компьютер ищет в своей памяти процедуру с именем SPIRAL и запускает ее копию. Причем переменная A во второй копии - "своя" и отличается от той, что была в первой копии процедуры SPIRAL. Эта идея создания копий остается справедливой и для всех последующих рекурсивных вызовов. |
||
| Второй вызов: | SPIRAL 15 | |
| Вторая строка: | FD :A | Черепашка продвигается вперед на 15 шагов Не забываем, что переменная А здесь - "своя"! |
| Третья строка: | RT 90 | Черепашка поворачивается направо на 90 градусов |
| Четвертая строка: | SPIRAL :A-5 | Вызывает процедуру SPIRAL и передает ей значение параметра 15-5=10 |
| Третий вызов: | SPIRAL 10 | |
| Вторая строка: | FD :A | Черепашка продвигается вперед на 10 шагов |
| Третья строка: | RT 90 | Черепашка поворачивается направо на 90 градусов |
| Четвертая строка: | SPIRAL :A-5 | Вызывает процедуру SPIRAL и передает ей значение параметра 10-5=5 |
| Четвертый вызов: | SPIRAL 5 | |
| Вторая строка: | FD :A | Черепашка продвигается вперед на 5 шагов |
| Третья строка: | RT 90 | Черепашка поворачивается направо на 90 градусов |
| Четвертая строка: | SPIRAL :A-5 | Вызывает процедуру SPIRAL и передает ей значение параметра 5-5=0 |
и тогда четвертый вызов будет предпоследним, так как при пятом вызове:TO SPIRAL :A IF :A<5 [STOP] FD :A RT 90 SPIRAL :A-5 END
| Пятый вызов: | SPIRAL 0 | |
| Вторая строка: | IF :A<5 [STOP] | Значение А равно нулю, а значит меньше 5 и условие остановки выполнено. Процедура останавливается. |
Но что же происходит с предыдущими копиями? После завершения пятая копия передает управление процедуре, ее вызвавшей, то есть четвертой копии, и команде, следующей непосредственно за командой вызова процедуры, но в нашем случае непосредственно за командой вызова следует END, и четвертая копия также завершает работу, передавая управление третьей копии процедуры SPIRAL. Третья копия также завершает работу, передавая управление второй копии, а та - первой копии. Так как первая копия является исходной процедурой и она не вызывалась никакой другой, то программа в целом завершает работу. На экране мы видим четыре звена спирали длиной 20, 15, 10 и 5 черепашьих шагов.
Таким образом, во время работы нашей программы в каждый момент в памяти компьютера находилось несколько незавершенных копий исходной процедуры. Их количество определяет глубину рекурсии или глубину рекурсивных вызовов.
2. Хвостовая и вложенная рекурсии
На поверхностный взгляд может показаться, что рекурсия - это просто аналог циклической организации алгоритма. На самом же деле идея рекурсии много сложнее и глубже.
Только что мы рассмотрели так называемую хвостовую рекурсию, когда рекурсивный вызов является последней командой процедуры. А теперь сравним две очень похожие друг на друга процедуры.
TO SPIRAL1 :A IF :A<5 [STOP] FD :A RT 90 SPIRAL1 :A-5 END |
TO SPIRAL2 :A IF :A<5 [STOP] SPIRAL2 :A-5 FD :A RT 90 END |
Мы видим, что процедура SPIRAL2 отличается от предыдущей только тем, что, в отличие от SPIRAL1, в этой процедуре рекурсивный вызов предшествует командам
однако при этом результаты выполнения процедур качественно различны. Чтобы понять, почему так происходит, разберем процедуру SPIRAL2 также детально, как мы это сделали с процедурой SPIRAL1.
| Первый вызов: | SPIRAL2 20 | |
| Вторая строка: | IF :A<5 [STOP] | Значение А больше 5 и условие остановки не выполнено. Процедура продолжает выполняться. |
| Третья строка: | SPIRAL :A-5 | Вызывает процедуру SPIRAL2 и передает ей значение параметра 20-5=15 |
| Четвертая строка: | FD 20 RT 90 | Команды не выполняются, но сохраняются в памяти компьютера |
| Второй вызов: | SPIRAL2 15 | |
| Вторая строка: | IF :A<5 [STOP] | Значение А больше 5 и условие остановки не выполнено. Процедура продолжает выполняться. |
| Третья строка: | SPIRAL :A-5 | Вызывает процедуру SPIRAL2 и передает ей значение параметра 15-5=10 |
| Четвертая строка: | FD 15 RT 90 | Команды не выполняются, но сохраняются в памяти компьютера |
| Третий вызов: | SPIRAL2 10 | |
| Вторая строка: | IF :A<5 [STOP] | Значение А больше 5 и условие остановки не выполнено. Процедура продолжает выполняться. |
| Третья строка: | SPIRAL :A-5 | Вызывает процедуру SPIRAL2 и передает ей значение параметра 10-5=5 |
| Четвертая строка: | FD 10 RT 90 | Команды не выполняются, но сохраняются в памяти компьютера |
| Четвертый вызов: | SPIRAL2 5 | |
| Вторая строка: | IF :A<5 [STOP] | Значение А не меньше 5 и условие остановки не выполнено. Процедура продолжает выполняться. |
| Третья строка: | SPIRAL :A-5 | Вызывает процедуру SPIRAL2 и передает ей значение параметра 5-5=0 |
| Четвертая строка: | FD 5 RT 90 | Команды не выполняются, но сохраняются в памяти компьютера |
| Пятый вызов: | SPIRAL2 0 | |
| Вторая строка: | IF :A<5 [STOP] | Значение А меньше 5 и условие остановки выполнено. Процедура останавливается и передает управление в четвертую копию. |
В отличие от предыдущего случая, четвертая копия при этом не завершает свою работу, так как управление передается команде, следующей за рекурсивным вызовом, а именно команде FD 5, а затем RT 90. Только после этого четвертая копия процедуры SPIRAL2 завершает свою работу, передавая управление третьей копии, команде FD 10, а затем RT 90. После этого третья копия завершает работу и выполняются команды FD 15 RT 90 второй копии. После ее завершения выполняются команды FD 20 RT 90 первой копии и вся программа в целом завершает свою работу.
Таким образом, при вызове процедуры SPIRAL2, мы увидим "раскручивающуюся" спираль, а при вызове процедуры SPIRAL1 спираль будет "закручиваться".
Можно провести следующую аналогию. Представим себе, что мы проходим анфиладу комнат, выполняем предписанные нам действия, распахиваем двери все в новые и новые комнаты и в каждой из них оставляем записку на память. Пройдя комнаты до конца, мы возвращаемся, выполняя указания, на оставленных нами записках, и плотно закрывая за собой двери. Заметим при этом, что указания выполняются в порядке, обратном тому, в котором они оставлялись.
Если в процедуре рекурсивный вызов не является завершающей инструкцией, то такая рекурсия называется вложенной.
Вопросы
- Какую процедуру мы называем рекурсивной?
- Что такое условие остановки и является ли оно необходимой составляющей рекурсивной процедуры?
- Что произойдет, если рекурсивный вызов будет предшествовать условию остановки?
- Что такое глубина рекурсии?
- Какую рекурсию мы называем хвостовой?
- В чем существенное различие хвостовой и вложенной рекурсий?
Задания
- Напишите процедуру, содержащую рекурсивный вызов в конце (хвостовая рекурсия), для рисования раскручивающейся спирали, когда Черепашка движется "изнутри наружу", с каждым поворотом увеличивая длину звена спирали.
- Напишите процедуры для треугольной закручивающейся и раскручивающейся спиралей с углом поворота 120 градусов.
- Напишите процедуры для пяти- и шестиугольной раскручивающихся спиралей.
- Напишите процедуру для закручивающихся спиралей, у которых изменяется длина звена и угол поворота.
- Напишите программу, которая, сначала рисует закручивающуюся направо спираль, а затем, используя команду PENERASE, стирает ее. Указание: для этого надо описать процедуру для раскручивающейся налево спирали.
- Напишите программу для многократного рисования-стирания треугольной, пяти- и шестиугольной спиралей.
4. Более сложные примеры рекурсии
1 2 3 4 5 6 7 8
Рис.4-1
Рекурсивная графика на основе правильных многоугольников.Посмотрите на рисунки. Наверное, поначалу трудно представить, что эти замысловатые формы могут быть получены с помощью несложных и очень коротких программ. Скоро мы с вами в этом убедимся, и добавим к нашей галерее не менее прекрасные образцы. Остановимся на первом рисунке "соты".
Рис. 4-2
"Соты" из правильных шестиугольниковКогда мы собираемся создать рекурсивный рисунок, очень важно описать его словесно. Для разных словесных описаний алгоритмы рисования могут быть совершенно различны. Как мы могли бы описать данный рисунок? Попытайтесь дать свои определения, а мы сейчас остановимся на следующем.
Это правильный шестиугольник, на каждой стороне которого нарисован правильный шестиугольник, на каждой стороне которого нарисован правильный шестиугольник, и так далее.
Выделим "центральный" шестиугольник А, окруженный двумя слоями таких же шестиугольников. Конечно, мы можем не останавливаться на трех слоях (шестиугольник А также является слоем из одного элемента) и в идеале число слоев может быть бесконечно, но не бесконечен наш экран, на который мы воводим картинку. Число слоев определяет глубину рекурсии. Внутренний слой - это третий уровень (шестиугольник A), самый внешний - имеет номер 1, и номер 2 имеет промежуточный слой. Интересно поразмыслить над вопросом, что будет, если глубина рекурсии равна одному или нулю. Как вы думаете?
Итак, мы знаем, что правильный шестиугольник можно нарисовать двумя способами
То есть, в первом случае мы имеем "правые", а во втором - "левые" шестиугольники. Каким фигурам отдать предпочтение? Это не имеет значения, важно лишь, что для рекурсивной графики мы должны использовать только один тип, например, только "правые" шестиугольники.
Также очень важно разумно выбрать начальную точку и начальную ориентацию для Черепашки. Часто правильный выбор этих параметров определяет успех всей программы, а неправильный, наоборот, может завести в дремучие и непролазные дебри.
В нашем случае удобно начать рисовать из точки, отмеченной черным кружком, при начальной ориентации Черепашки на Север.Обозначив длину стороны шестиугольника через :SIZE, сделаем первый шаг: FD :SIZE. Повернув Черепашку направо на 180 градусов, мы оказываемся по отношению к шестиугольнику B, находящемуся на втором уровне, в той же позиции, в какой мы находились изначально по отношению к A. Разница лишь в том, что теперь шестиугольник B является центральным для второго уровня. Это очень важный момент. Давайте сделаем паузу и внимательно рассмотрим рисунок, обдумывая только что сказанное.
Таким образом, нам опять надо нарисовать шестиугольник, на каждой стороне которого - шестиугольник, но уже на втором уровне. Следуя этой логике, следующим шагом мы выходим уже на первый уровень. Повторяя все это 6 раз, по числу сторон центрального шестиугольника, мы, очевидно, завершим наше удивительное путешествие. Надо только учесть, что когда Черепешка завершает свой путь вокруг шестиугольника более низкого уровня и возвращается на более высокий уровень, например, с первого на второй, для продолжения маршрута ее следует сначала развернуть на 180 градусов, а затем - еще на 60, как показано на рисунке:
Итак, может быть предлжен следующий алгоритм (но могут быть и другие!):
TO MAIN CS HT DO 20 3 END TO DO :SIZE :LEVEL IF :LEVEL<1 [STOP] REPEAT 6[ FD :SIZE RT 180 DO :SIZE :LEVEL-1 RT 180 RT 60] END
Название говорит о том, что процедура является главной и именно с нее начинает работу вся программа в целом. Чистая косметика. Очищается экран и Черепашка прячется, так как она не является частью нашего рисунка Рекурсивная процедура, рисующая три уровня шестиугольников с длиной стороны, равной 20. Запустив программу на компьютере, убедимся, что она работает. Однако, нельзя сказать, что процедура DO выглядит безукоризненно, список команд, которые нужно повторять в цикле REPEAT, слишком длинный. Иногда этот список еще длиннее и может составлять несколько строк. Чтобы улучшить вид нашей процедуры, опишем команды цикла отдельной процедурой:
TO MAIN CS HT DO 20 3 END TO DO :SIZE :LEVEL IF :LEVEL<1 [STOP] REPEAT 6[ SHAPE :SIZE :LEVEL RT 60] END TO SHAPE :SIZE :LEVEL FD :SIZE RT 180 DO :SIZE :LEVEL-1 RT 180 ENDРазрабатывая рекурсивные процедуры в будущем, мы убедимся в том, что, как правило, не возникает проблем при написании процедуры MAIN и DO. Основные трудности нам придется преодолевать при разработке процедуры SHAPE.
5. Задания
- Рассмотрите внимательно рисунки 1-4 и составьте их словесное описание.
- В рассмотренной программе "соты" складывались из шестиугольников. Какие параметры программы и как следует изменить для треугольных, квадратных, пятиугольных, N-угольных "сот"?
- Напишите и отладьте процедуры, которые воспроизводят рекурсивные графические изображения, представленные на рисунках 1-4.
- Рассмотрите внимательно рисунки 5-8 и составьте их словесное описание.
- Какие параметры многоугольников и как меняются при переходе от одного уровня рекурсии к другому? Как это повлияет на входные параметры рекурсивной процедуры при повторных вызовах, останется ли параметр :SIZE неизменным?
- Попробуйте применить прием, использованный в "сотах", когда командами FD :SIZE RT 180 мы перемещали Черепашку в исходную позицию для шестиугольника B, находящегося на более низком уровне. Какие команды следует применить в этом случае?
- Напишите и отладьте процедуры, которые воспроизводят рекурсивные графические изображения, представленные на рисунках 5-8.
Решения
Работа над страницами не закончена. За кадром осталась работа с цветом, многие интересные образцы рекурсивной графики, фракталы.
Буду благодарна за советы, замечания и предложения. Ольга Тузова. E-mail: olgatu@ort.spb.ru
