|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Тема 3. Рекурсивные процедуры
Введение Само слово «рекурсия» означает возврат обратно. С рекурсией в жизни мы встречаемся довольно часто. Достаточно поставить два зеркала друг против друга, и можно получить «рекурсивные» отражения одного и того же в самом себе. Можно встретить и рекурсивные стихи. Например, известная поэма о попе:
У попа была собака, он ее любил. Она съела кусок мяса, он ее убил! В землю закопал, на табличке написал: У попа была собака, он ее любил. Она съела кусок мяса, он ее убил! В землю закопал, на табличке написал: …
Или песенка о царе:
Жил был царь, У царя был двор, На дворе – мочало, Начинай сказывать сначала. Жил был царь, У царя был двор,
Начинай сказывать сначала. …
Можно встретить и рекурсивные картины. Есть даже специальный раздел графики – фрактальная, в основе которой рекурсивное изображение одного и того же узора в самом себе.
Понятие рекурсивной процедуры Так что же такое рекурсивные процедуры? Рекурсия - это такая организация алгоритма, при которой процедура обращается к самой себе. Сама процедура называется рекурсивной. Что же получится, если в процедуре записать обращение к самой себе? Чтобы выполнить этот вызов, компьютер ищет в своей памяти процедуру с указанным именем и запускает ее копию. Причем переменные, значения которых передаются в копию процедуры, - " свои" и отличаются от тех, что были в первой копии процедуры. Эта идея создания копий остается справедливой и для всех последующих рекурсивных вызовов. Упражнение 1. Создайте процедуру, рисующую квадрат со стороной: а.
Это квадрат: а по повтори 4 [вп: а пр 90] Конец
При вызове этой процедуры, например в таком виде: квадрат 100, черепашка нарисует квадрат со стороной 100 шажков. Теперь попробуем превратить эту процедуру в рекурсивную. Вставим вызов этой же процедуры в конец нашей программы:
Это квадрат: а по повтори 4 [вп: а пр 90] Квадрат: а Конец
Тогда вызов процедуры квадрат 200 заставит черепашку рисовать квадрат бесконечно, пока мы не остановим выполнение процедуры нажатием клавиш Ctrl+Break.
Упражнение 2 Попробуем усложнить задачу. Заставим черепашку не просто повторять процедуру, а изменим для следующего шага рекурсии параметр рисования. Изменим строку рекурсивного вызова: Квадрат: а - 5 Тогда в следующем вызове процедуры нарисуется уже квадрат со стороной на 5 шажков меньше, а в следующем – опять на 5 шажков меньше и т.д.
Чтобы проследить процесс выполнения такой процедуры, замените команду вп: а командой плавно: а 1. По этой команде черепашка будет тоже двигаться вперед, но со скоростью 1 шаг и вы увидите процесс более подробно. Как только сторона квадрата станет отрицательной, черепашка начнет двигаться уже не вперед, а назад, и получится симметричный рисунок расширяющихся квадратов. Не забудьте нажать Ctrl+Break, чтобы остановить черепашку. В начало Управляемая рекурсия
В предыдущих упражнениях процесс, начатый в рекурсивной процедуре можно было остановить только прервав работу программы. Управлять работой рекурсивных процедур можно с помощью команд с условиями.
Упражнение 3 Попробуйте усовершенствовать программу из упражнения 2. Вставьте условие, останавливающее выполнение процедуры. Например, такое: если: а < -200 [стоп]
Примеры управляемых рекурсий
Пример 1 Усовершенствуем программу в Упражнении 3. После рисования квадрата будем поворачивать черепашку на малый угол. Таким образом, каждый следующий квадрат будет не только меньше предыдущего, но и повернут относительно него на 1 градус.
Это кв: а по если: а < -200 [стоп] повтори 4 [плавно: а 1 пр 90] пр 1 Кв: а - 5 Конец
Получится довольно милая картинка:
Пример 2 Попробуем изобразить спираль с помощью рекурсивной программы. Для этого будем рисовать ее звенья с уменьшающейся длинной, повернутые на 90 градусов друг относительно друга.
Это спир: а если: а < 2 [стоп] Вп: а пр 90 Спир: а - 5 Конец
Упражнение 4 Придумайте сами и осуществите в проекте свою рекурсивную процедуру с управляемым выходом. Создайте кнопку, включающую рисование рекурсивного узора.
Упражнение 5 Косвенная рекурсия
Пусть нам нужно сначала нарисовать спираль, а потом ее стереть. Рисовать спираль мы уже умеем. Чтобы стереть спираль, надо изменить цвет пера черепашки командой нц на цвет фона. Если вы рисуете на белом фоне, то это сделает команда нц 0. В процедуре стирания спирали нужно пройти по спирали в другую сторону, т.е. не уменьшать, а увеличивать длину звена спирали. Не забудьте повернуть черепашку еще раз на 90 градусов перед организацией стирания. Учтите, что в обратной спирали нужно поворачиваться налево, а не направо, как в прямой. Попробуйте связать две процедуры друг с другом. Для этого вставьте в строчку с условием окончания процедур вызов противоположных процедур. Тогда получится бесконечный процесс рисования и стирания спирали.
Популярное:
|
Последнее изменение этой страницы: 2017-03-03; Просмотров: 623; Нарушение авторского права страницы
На дворе – мочало, 
