Рекурсия — одна из самых интересных, красивых и в то же время — сложных и неоднозначных тем в курсе изучения Лого.

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

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

Рекурсия с отложенными командами может приводить к удивительным результатам. Посмотрите архив Лого-форума в Интернете (http://gsndev.org/archives/logo-l/1297/) — с каким упоением и азартом маститые программисты и университетские профессора разрабатывают и обсуждают чудеса рекурсивной графики. И надо видеть глаза ребенка, когда черепашка вычерчивает причудливое рекурсивное кружево снежинки Коха или треугольника Серпинского. В глазах — восторг и удивление: “Вот это да! А как это так получается?”

Где еще можно встретить такую ситуацию — ученик сам уверенно пишет программу, сам инструктирует черепашку, что и как делать, а потом искренне удивляется, почему это она все выполнила, как надо?

Действительно, научить ребенка строить сложные рекурсивные рисунки, следуя заданным алгоритмам (сначала делай так, а потом — вот так…), — проблема более простая, чем объяснить ему, почему именно так и надо делать. Можно, конечно, ограничиться подобным подходом, он решает немало образовательных задач: развивает наблюдательность, шлифует навыки разработки алгоритмов, знакомит с понятием рекурсия, с фракталами, в какой-то степени повышает заинтересованность и мотивацию к изучению программирования и Лого в частности. Но такое решение представляется не только однобоким, но и тупиковым: вряд ли, не понимая механизма работы рекурсии, ученик справится с рекурсивной обработкой слов и списков, кроме того, переходя в другую среду программирования, на другие языки, изучение рекурсии придется начинать заново, с чистого листа.

В данной статье предлагается методика изучения рекурсии в среде Лого в 6–7-х классах средней школы, основанная на понимании механизмов рекурсии. Рассматриваются учебные задания разного уровня сложности. Задания повышенного и высокого уровней сложности могут быть использованы в специализированных классах, на занятиях кружков и факультативов, а также при индивидуальной работе с учениками.

Рекурсивные задачи на клетчатом поле

Предпосылки

В прошлом году команда пяти- и шестиклассников нашей школы изучала “Азы программирования” в Роботландском университете, которым руководит Александр Александрович Дуванов. Нестареющий учебный исполнитель Кукарача трудился на клетчатом поле, уверенно решая далеко не легкие задачи. Дошло дело и до рекурсии.

Решать задачи без понимания механизмов работы рекурсии в среде Кукарачи невозможно. Были испробованы различные методические приемы. Один из них, вовлекающий детей в активную групповую деятельность, оказался наиболее успешным и позволил юным программистам не только разобраться в готовых решениях, но и самостоятельно решить трудные задачи. Тогда у меня возникла идея смоделировать аналог среды Кукарачи в ЛогоМирах и применить те же методы и методики для начального изучения рекурсии. Затем, уже на построенном фундаменте, можно перейти к рекурсивной обработке слов и списков. После этого сложная рекурсивная графика уже становится более понятной, и изучение ее с педагогической точки зрения более оправданно.

Подготовительный этап

Готовим среду решения задач: Лого-проект с рисунком клетчатого поля. Разрабатываем также процедуры, которые сформируют на клетчатом поле различные “проблемные” ситуации для черепашки. Каждая такая ситуация — одна или несколько задач, требующих рекурсивного решения. Вызов этих процедур удобно привязать к кнопкам (процедуры для среды ЛогоМиры 3.0 приведены в приложении).

Наша среда-заготовка может выглядеть, например, так.

 

Рис. 1

Размер клеточек — 40 х 40 шагов. Черепашку зовут t1. Для того чтобы лучше наблюдать за действиями черепашки при решении задач, установим режим “Медленно” на вкладке “Процессы”.

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

Детали процесса подготовки зависят от оснащения класса. В моем классе есть проектор и интерактивная доска. Картинка выводится на монитор и на интерактивную доску. Один из учеников (“Исполнитель”, заместитель черепашки) фиксирует на доске электронным карандашом последовательные перемещения черепашки. Если такого оборудования нет, можно использовать, например, бумажный вариант поля и какими-либо предметами моделировать “проблемные” ситуации и перемещение черепашки.

Урок

На экране первая задача. (Напомню, что идеи задач заимствованы из учебника А.А. Дуванова “Азы программирования”.)

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

Рис. 2

Требуется дойти до красной клетки, перекрасить ее цветом поля (желтым — № 45) и вернуться на исходную позицию.

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

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

Подводим учеников к следующему решению:

1) пройти вперед на 40 шагов (в центр соседней клеточки),

2) если цвет под черепашкой красный, то перекрасить клетку в желтый цвет и закончить выполнение алгоритма,

3) выполнить все еще раз с самого начала.

На языке Лого процедура выглядит так:

to zadacha1

fd 40

if colorunder = 15 [setc 45 fill

setc 9 stop]

zadacha1

end

Раздаем карточки с решением. Карточек должно быть столько, сколько раз будет вызываться процедура (на одну больше, чем количество клеточек между клеткой, где находится черепашка, и красной клеткой). Ученик, выполняющий роль черепашки (“Исполнитель”), работает у доски.

Командует ученик, у которого карточка с номером 1 (первый вызов процедуры), ученик у доски выполняет его команды:

— Вперед на 40 шагов. — На доске делается соответствующая отметка.

— Проверить цвет под черепашкой. Он красный? — Нет.

— Вызываю новую копию процедуры.

Управление черепашкой передается ученику с карточкой номер 2. Диалог повторяется. Затем командует ученик с карточкой номер 3 и так далее. Цепочка обрывается, когда при выполнении копии процедуры черепашка оказывается на красной клетке. Теперь надо свернуть цепочку в обратном порядке. Ученик, назовем его “Последний вызов”, после команды перекраски объявляет, что работа его копии процедуры закончена и управление передается тому, кто его вызвал. “Предпоследний вызов” также заканчивает работу и передает управление вызвавшему его товарищу. Все заканчивается, когда управление оказывается у первого номера. Обращаем внимание учеников на вторую часть: цепочка процедур должна быть не только развернута, но и свернута в исходное состояние.

Для объяснения этого этапа применяют различные образные метафоры. Рекурсивный процесс сравнивают, например, с проходом через анфиладу комнат: дойдя до конца, надо вернуться обратно, закрывая за собой двери. Другая метафора — матрешки. Добравшись до самой маленькой, надо закрыть все открытые матрешки так, чтобы осталась только первая.

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

to zadacha1_1

fd 40

if colorunder = 15 [setc 45 fill

setc 9 bk 40 stop]

zadacha1_1

bk 40

end

Анализируем работу процедуры по описанной выше схеме.

Когда “Последний вызов” возвращает управление “Предпоследнему вызову”, тот должен передать “Исполнителю” оставшиеся у него команды, а именно
bk 40. Только после этого он заканчивает работу и передает управление вызвавшему его товарищу. Тот также должен передать “Исполнителю” команду bk 40 перед тем, как закончить работу своей копии. Таким образом, отложенная команда bk 40 выполнится столько раз, сколько было копий нашей процедуры, и черепашка вернется на исходную позицию. Обращаем внимание учеников на то, что команда bk 40 должна выполниться и в последнем вызове процедуры, когда черепашка находится на красной клетке. Иначе она не вернется в исходную позицию. Поэтому на красной клетке черепашка не только перекрашивает клеточку, но и делает шаги назад.

Графически рекурсивный процесс может быть описан следующей схемой.

Рис. 3

На экране вторая задача.

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

Рис. 4

Подводим детей к решению, например, такому:

to zadacha2

fd 40 rt 90 fd 40 lt 90

if colorunder = 65 [

setc 45 fill setc 9

rt 90 bk 40 lt 90 bk 40]

zadacha2

rt 90 bk 40 lt 90 bk 40

end.

Но на достигнутом не останавливаемся. Решение плохо структурировано. Советуем выделить подъем и спуск на одну ступеньку в отдельную процедуру. Решение принимает вид:

to zadacha2

step_up ; шаг вверх

if colorunder = 65 [setc 45 fill

setc 9 step_down]

zadacha2

step_down ; шаг вниз

end.

to step_up

; шаг вверх на одну ступеньку

fd 40 rt 90 fd 40 lt 90

end

to step_down

; шаг вниз на одну ступеньку

rt 90 bk 40 lt 90 bk 40

end

Анализируем решение “вручную”, как и в предыдущей задаче.

Для закрепления могут быть предложены такие задачи, как “Горка” и “Коридор”.

Горка	Коридор
Рис. 5	Рис. 6
Черепашка находится на левом склоне, на неизвестном уровне. Надо дойти до вершины, перекрасить зеленую клеточку в желтый цвет (отметиться на вершине) и вернуться на первоначальный уровень по правому склону.	Черепашка находится внутри красного коридора в неизвестной точке, но под красной клеткой (так, как показано на рисунке). Требуется дойти до конца коридора, перекрасить в желтый цвет зеленые клеточки и вернуться в исходную клетку.

Рекурсивная обработка слов и списков

Как известно, язык Лого “вырос” из языка программирования LISP (LISt Processing language) — языка обработки списков — и сохранил мощные инструменты для работы со словами и списками.

Со словами можно поиграть, отбрасывая и переставляя буквы, объединяя несколько слов в одно и получая новые слова. Интересными являются задания на шифрование слов, поиск палиндромов (слов-перевертышей, одинаково читающихся слева направо и справа налево). В языке Лого числа также можно рассматривать как слова. Это дает нам возможность, применяя инструменты работы со словами, искать “счастливые” числа, решать задачи на делимость и перевод чисел из одной системы счисления в другую [2].

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

Примеры задач первого уровня

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

2. Чепуха. Составляется два списка: вопросы и ответы. Программа наугад выбирает пару: вопрос — из одного списка, ответ — из другого.

3. Англо-русский и русско-английский словарь. Составляется словарь: список списков. Списки — пара слов: русское слово и его английский аналог. Программа позволяет вводить слово на русском или английском языке и с помощью простого поиска находить второе слово из пары.

4. Телефонная книга. Задача аналогична предыдущей, отличается только содержанием списков, в которых можно хранить фамилии, имена, телефоны друзей, их дни рождения.

Примеры задач повышенного уровня сложности

1. Сложные игры со словами и списками (фигурный вывод в текстовое окно, “Балда” и другие).

2. Удаление элемента списка (буквы слова).

3. Фильтрация слова или списка.

4. Сортировка списков, в том числе быстрая сортировка.

5. Быстрый поиск элемента списка.

Задачи (2–5) можно рассматривать как отдельные упражнения, но более содержательным подходом будет их решение в рамках учебного проекта по созданию базы данных и разработки соответствующей СУБД. Пример базы данных в Лого-среде можно найти на диске с дистрибутивом ЛогоМиры 2.0 в папке Проекты\Пособия.

Рассмотрим рекурсивные решения некоторых из упомянутых выше задач.

to word1 победа if empty? "победа [stop] print "победа word1 "обеда end	Первый вызов процедуры. Условие остановки не выполнено. В текстовое окно выводится слово "победа. Рекурсивный вызов с новым значением параметра
to word1 "обеда if empty? "обеда [stop] print "обеда word1 "беда end	Второй вызов процедуры. Условие остановки не выполнено. В текстовое окно выводится слово "обеда. Рекурсивный вызов с новым значением параметра
to word1 "беда if empty? "беда [stop] print "беда word1 "еда end	Третий вызов процедуры. Условие остановки не выполнено. В текстовое окно выводится слово "беда. Рекурсивный вызов с новым значением параметра
…	…
to word1 "а if empty? "а [stop] print "а word1 " end	Шестой вызов процедуры. Условие остановки не выполнено. В текстовое окно выводится слово "а. Рекурсивный вызов с пустым словом
to word1 " if empty? " [stop] … end	Последний вызов процедуры. Условие остановки выполнено. Процедура заканчивает работу. Управление передается шестой копии процедуры. Рекурсивная цепочка начинает сворачиваться

Фигурный вывод слова в текстовое окно

Именно с этих упражнений начинает объяснение механизмов работы рекурсии профессор университета Беркли Брайен Харви (Brian Harvey) в своем трехтомном фундаментальном труде Computer Science Logo Style [3].

Для объяснения работы программ и самостоятельного поиска решений воспользуемся приемом, описанным в разделе “Рекурсивные задачи на клетчатом поле”.

Задача 1 (подготовительная). Вывести слово в текстовое окно перевернутым треугольником. Например, если на вход программы подается слово “победа”, то в текстовом окне должно появиться:

победа

обеда

беда

еда

да

а

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

Основное отличие рассматриваемых задач от тех, которые мы решали на клетчатом поле, — наличие в рекурсивной процедуре параметра. К этому моменту дети должны не только освоить примитивы работы со словами, но и хорошо понимать роль входных параметров процедуры. В нашей задаче параметром будет слово.

Обсуждая задачу, мы приходим к следующему алгоритму:

1. Напечатать слово.

2. Оставить слово без первой буквы.

3. Выполнить все с самого начала.

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

В конце концов приходим к следующему решению:

to word1 :s

if empty? :s [stop]

print :s

word1 bf :s

end

Раздаем пронумерованные карточки с решением, но вместо параметра оставляем свободное место, куда дети будут записывать те значения, с которыми выполняется вызов их копии процедуры (cм. табл. выше).

Задача 2. Вывести слово в текстовое окно так, чтобы рисунок напоминал два треугольника, склеенных в вершине:

победа

обеда

беда

еда

да

а

а

да

еда

беда

обеда

победа

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

Приходим к следующему решению:

to word2 :s

if empty? :s [stop]

print :s

word2 bf :s

print :s

end

Проверяем его сначала “вручную”, потом на компьютере с различными значениями входного параметра. Для закрепления материала решаем две дополнительные задачи.

Задача 3. Вывести слово в текстовое окно треугольником.

Подсказка: нужно изменить процедуру word2 так, чтобы проработали только отложенные команды.

a

да

еда

беда

обеда

победа

Задача 4. Вывести слово в текстовое окно половинкой ромба.

Подсказка: главная процедура сначала вызывает процедуру, печатающую слово треугольником, а затем — печатающую слово перевернутым треугольником.

a

да

еда

беда

обеда

победа

победа

обеда

беда

еда

да

а

Следующие задачи похожи на предыдущие, но рекурсивные процедуры потребуют от нас новых действий:

· использование двух входных параметров,

· вывод в текстовое окно пробела,

· использование команды insert вместо команды print.

Напомним, что при выполнении команды insert курсор остается в той же строке вывода и следующая команда print или insert продолжает вывод, не переводя курсор на новую строку. Пробел выводится командами:

print |" | или insert |" | .

Задача 5. Вывести слово в текстовое окно перевернутым равнобедренным треугольником (слово должно содержать нечетное число символов):

комар

ома

м

Заметим, чтобы треугольник был равнобедренным, следует использовать моноширинный шрифт, например, “Courier”.

Обсуждаем особенности задачи. Во-первых, новое слово получают из предшествующего отбрасыванием не только первой, но и последней буквы. Во-вторых, перед выводом слова в текстовое окно надо напечатать некоторое количество пробелов: сначала 0, потом 1, потом 2... То есть количество пробелов соответствует порядковому номеру копии рекурсивной процедуры. Таким образом, приходим к решению:

to word5 :s :n

if empty? :s [stop]

repeat :n [insert |" | ]

print :s

word5 bf bl :s :n + 1

end

При первом вызове процедуры параметр n равен нулю, например, word5 "комар 0.

Закрепляем тему тремя задачами, аналогичными задачам 2–4.

Задача 6. Вывести слово в текстовое окно двумя склеенными вершинами треугольников:

комар

ома

м

м

ома

комар

Задача 7. Вывести слово в текстовое окно равнобедренным треугольником:

м

ома

комар

Задача 8. Вывести слово в текстовое окно “диадемой”:

м

ома

комар

комар

ома

м

Если фигурный вывод текста на экран можно рассматривать как “упражнение для упражнения”, то удаление символа слова или элемента списка, сортировка списка — задачи, необходимые для управления любой базой данных. Это непростые задачи, их решение может оказаться не по силам ученикам. Возможный выход — предложить для использования готовые процедуры. Ученику при этом остается немало сложных задач для самостоятельного решения: организация взаимодействия пользователя с этими процедурами, хранение и добавление данных.

Удаление заданного символа из слова (элемента из списка)

Для решения этой задачи ученики должны быть знакомы с примитивом output (в русской версии — выход). Эта команда применяется в процедуре-функции, она заканчивает выполнение процедуры. Значением функции является значение аргумента команды output.

Предположим, что из слова "qwertyuiop надо удалить символ "q. Наша процедура должна вернуть нам слово без первого символа.

Если же надо удалить символ "w, то сначала отделяем первый символ, в оставшемся слове ищем заданный символ — он оказывается первым, удаляем его и обработанное слово соединяем с первым (отделенным) символом.

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

Если удаляемый символ — первый в слове, то процедура должна вернуть заданное слово без первой буквы.

Иначе процедура должна вернуть соединение первого символа слова и слова, рекурсивно обработанного нашей процедурой:

to delete_one_w :s :a

; :s — заданное слово

; :a — заданный символ

if (first :s) = :a [output bf :s]

output word first :s delete_one_w bf :s :a

end

У такой процедуры есть недостаток: если заданный символ не содержится в слове, то завершение процедуры будет аварийным.

Добавим еще одну проверку:

to delete_one_w :s :a

; :s — заданное слово

; :a — заданный символ

ifelse member? :a :s [

if (first :s) = :a [output bf :s]

output word first :s delete_one_w bf :s :a]

[output :s]

end

Аналогичная процедура может применяться для удаления элемента списка:

to delete_one_l :l :s

; :l — заданный список

; :s — заданный элемент списка

ifelse member? :a :s [

if (first :l) = :s [output bf :l]

output se first :l delete_one_l bf :l :s]

[output :l]

end

Фильтрация слова (списка)

Формулировки заданий такого рода могут быть разными.

Пример 1. Разработать процедуру, удаляющую в заданном слове все гласные буквы (или все цифры).

Вариант решения:

to filtr_w :s :l

if empty? :s [op []]

if not member? first :s :l

[op word first :s filtr_w bf :s :l]

op filtr_w bf :s :l

end

Вызов процедуры:

print filtr_w "рекурсия [а е и о у э ы ю я]

Результат: ркрс

Пример 2. В заданном списке, содержащем слова и числа, оставить только числа.

Вариант решения:

to filtr_numbers :l

if empty? :l [op []]

if number? first :l [op se first :l filtr_numbers bf :l]

op filtr_numbers bf :l

end

Вызов процедуры: print filtr_numbers [пирожки 25 пицца 100 блинчики 65]

Результат: 25 100 65

Сортировка числового списка

Изложенная ниже процедура приведена в статье [1].

Процедура соответствует следующему алгоритму:

В списке выделяем первое число. Оставшуюся часть списка делим на две части (два списка) — в первую часть перемещаем все числа, меньшие выделенного, во вторую — все остальные. Первая часть — голова списка, вторая — хвост списка. Затем отдельно сортируем “голову” и “хвост” и объединяем отсортированные списки.

to sort1 :l

if empty? :l [op :l]

local "h_t ; вводим локальную переменную

make "h_t head_tail first :l bf :l

; вызывается процедура (head_tail), делящая список на две части

op (se sort1 first :h_t first :l sort1 last :h_t)

end

to head_tail :n :l

local "l1

make "l1 []

local "l2

make "l2 []

repeat count :l

[ifelse (first :l) < :n

[make "l1 lput first :l :l1][make "l2 lput first :l :l2] make "l bf :l]

op list :l1 :l2

end

Для сортировки списка, состоящего из слов, при сравнении надо использовать числовой код символов:

to head_tail1 :n :l

local "l1

make "l1 []

local "l2

make "l2 []

repeat count :l

[ifelse (ascii first first :l) < ascii first :n

[make "l1 lput first :l :l1][make "l2 lput first :l :l2] make "l bf :l]

op list :l1 :l2

end

Заметим, что это — упрощенная процедура сортировки, здесь слова сортируются только по первой букве, без учета второй и последующих.

Рекурсивная графика

Снежинка Коха

Рис. 7

Рекурсивная графика воспринимается как чудо не только детьми, но и взрослыми. Однако после задач “Рекурсия на клетчатом поле” и рекурсивной обработки слов нам вполне по силам раскрыть тайну чудесных рекурсивных построений. Начнем с широко известного изображения — снежинки Коха, кривой, названной в честь шведского математика Нильса Фабиана Коха (1870–1924). Для построения кривой используются два геометрических объекта: отрезок прямой и ломаная из четырех звеньев. Каждое звено в три раза меньше исходного отрезка.

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

Рис. 8

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

Наше изображение (кривая) растет и видоизменяется с каждым мгновением (для кривой мгновение — год). Инициатор — это новорожденная кривая. Ей 0 лет. Генератор — кривая через год после рождения. Покажите ученикам, как выглядит кривая через 2 года, 3, 4... Такие формулировки, возможно, недостаточно строги, но упрощают понимание заданий.

Не будем ожидать от детей самостоятельного решения задачи — построение кривой Коха произвольного “года жизни”.

Раздаем детям карточки с текстом процедуры:

to koch :a :n

;a — длина кривой

;n — "возраст" кривой

if :n = 0 [fd :a stop]

koch :a / 3 :n — 1 lt 60

koch :a / 3 :n — 1 rt 120

koch :a / 3 :n — 1 lt 60

koch :a / 3 :n — 1

end

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

Вызываем процедуру (первый вызов) с параметрами, например, a = 90, n = 2.

to koch 90 2

if 2 = 0 [fd 90 stop]

koch 30 1 lt 60

koch 30 1 rt 120

koch 30 1 lt 60

koch 30 1

end

Условие остановки не выполнено (2 не равно 0), и мы вызываем на выполнение копию процедуры с новыми параметрами:

to koch 30 1

if 1 = 0 [fd 30 stop]

koch 10 0 lt 60

koch 10 0 rt 120

koch 10 0 lt 60

koch 10 0

end

Выполнение остальных команд пока откладывается.

Условие остановки не выполнено (1 не равно 0), и мы вызываем копию процедуры с новыми параметрами:

to koch 10 0

if 0 = 0 [fd 10 stop]

...

end

Условие остановки выполнено, и выполняются команды fd 10 stop. Нарисуется маленький отрезок длины 10 и работа копии процедуры закончится, управление будет передано обратно в вызвавшую процедуру. Выполняются отложенные команды. Это команда
lt 60 и новый вызов копии процедуры koch 10 0. Снова выполняются команды fd 10 stop, и управление возвращается в koch 30 1. Таким образом, 4 раза будет вызвана процедура koch 10 0, которая нарисует 4 отрезка длиной 10 шагов каждый. Отрезки эти по отношению друг к другу будут размещены в форме генератора. Вызовы и возвраты выполняются по схеме:

Когда выполнение процедуры koch 30 1 закончится, управление будет передано в процедуру koch 90 2. Выполнятся первые отложенные команды: черепашка повернется налево на 60 градусов и опять вызовет про­цедуру koch 30 1. Что она нарисует, мы уже знаем. Опять вернемся в koch 90 2. Черепашка повернется на 120 градусов и в третий раз вызовет koch 30 1. После возврата из koch 30 1 черепашка повернется налево на 60 градусов и в последний раз вызовет koch 30 1.

В результате алгоритма мы получим следующую кривую.

Рис. 9

Соединив три ломаные треугольником, получим снежинку Коха.

to koch.main :a :n

repeat 3 [ koch :a :n rt 120]

end

Таким образом, алгоритм рисования рекурсивной снежинки может быть сформулирован так:

· обходим кривую-генератор, все повороты задаем командами поворота,

· каждый встречающийся на пути отрезок (инициатор) заменяем рекурсивным вызовом процедуры,

Общая схема выглядит следующим образом:

· первый параметр, отвечающий за размер снежинки, при рекурсивном вызове изменяется в соответствии с правилом, которое задает генератор (для снежинки Коха отрезок уменьшился в 3 раза),

· второй параметр, отвечающий за “возраст снежинки”, уменьшается на единицу,

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

· замкнутая кривая (снежинка Коха) получается соединением рекурсивно преобразованных отрезков в форме равностороннего треугольника.

Снежинка Мандельброта

Рис. 10

Эта кривая носит имя основателя фрактальной геометрии, бельгийского математика Бенуа Мандельброта. Нарисовать ее можно по такому же алгоритму, какой описан выше, используя два объекта — инициатор и генератор. Инициатором, как и прежде, является отрезок, а интегратор показан на рис. 11. При обсуждении построения обращаем внимание учеников на то, что ломаная-интегратор имеет 8 звеньев, а не 7. Все звенья должны быть одинаковыми. Звено, которое длиннее остальных, на самом деле — соединение двух одинаковых звеньев.

Таким образом, приходим к следующей процедуре.

Замкнутая кривая, снежинка Мандельброта, образуется соединением в виде квадрата четырех полученных фрагментов.

Для закрепления навыков предлагаем упражнения:

Рекурсивная и фрактальная графика. Дополнительные материалы

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

1. Weisstein, Eric W. Space-Filling Function. From MathWorld — A Wolfram Web Resource. http://mathworld.wolfram.com/Space-FillingFunction.html.

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

2. Златопольский Д.М. Кривые Гильберта и Серпинского, или Снова рекурсия. // Информатика, № 8, 9/1999.

Приводятся описания “всюду плотных в квадрате кривых” — кривых Гильберта и Серпинского и соответствующие программы на языках программирования Паскаль, QBasic, Си.

3. Тузова О.А. Лого как инструмент познания. http://school.ort.spb.ru/library/logo/texts/logo1_ru.pdf. Приводятся описания алгоритмов и программ на языке Лого построения различных рекурсивных изображений. Дополнением к статье [2] могут служить алгоритм и программа на языке Лого для построения кривой Серпинского (рис. 14).

to a :size :n

if :n < 1 [stop]

a :size :n - 1

seth 180 fd :size

b :size :n - 1

seth 90 fd :size

rt 90 fd :size

d :size :n - 1

seth 90 fd :size

a :size :n - 1

end

 

to b :size :n

if :n < 1 [stop]

b :size :n - 1

seth -90 fd :size

c :size :n - 1

seth 180 fd :size rt 90 fd :size

a :size :n - 1

seth 180 fd :size

b :size :n - 1

end

 

to c :size :n

if :n < 1 [stop]

c :size :n - 1

seth 0 fd :size

d :size :n - 1

seth -90 fd :size

rt 90 fd :size

b :size :n - 1

seth -90 fd :size

c :size :n - 1

end

 

to d :size :n

if :n < 1 [stop]

d :size :n - 1

seth 90 fd :size

a :size :n - 1

seth 0 fd :size

rt 90 fd :size

c :size :n - 1

seth 0 fd :size

d :size :n - 1

end

 

to main :size :n

a :size :n

seth 180 fd :size

b :size :n

seth -90 fd :size

c :size :n

seth 0 fd :size

d :size :n

seth 90 fd :size

end

Здесь a — правило построения правой верхней части рисунка, b — правой нижней, c — левой нижней и d — левой верхней. На рис. 14 представлены результаты работы главной процедуры main при n = 1, 2 и 3.

4. Златопольский Д.М. Кривая дракона. // Информатика, № 20/1999.

Дается наглядное описание кривой дракона (кривая Хартера — Хейтуэя), в том числе в терминах L-системы. Приводятся алгоритмы и программы на различных языках программирования.

5. Беленькая Н.Л., Сергеев Л.О. Фракталы. // Информатика, 2000.

Спецвыпуск газеты целиком посвящен этим замечательным объектам. Приводится описание различных фракталов (2- и 3-мерных) в терминах L-систем, на языках программирования Си и Бейсик. Это первый номер “Информатики”, вышедший в полноцветном варианте и содержащий около 30 красочных иллюстраций.

6. Тузова О.А. Волшебный мир рекурсии. http://school.ort.spb.ru/library/recurs/index.htm.

Учебно-методические материалы для занятий по теме “Рекурсивная графика в Лого-средах”.

7. Азевич А. Симфония фракталов. // Информатика, № 23, 24/2008.

Статья опубликована в разделе “В мир информатики”. В яркой, доступной форме описываются различные фракталы, их применение в компьютерной технике, телекоммуникации, физике и искусстве.
Дополнением к статье может служить описание рекурсивных деревьев на языке программирования Лого.

ПРИЛОЖЕНИЯ

Программа моделирования клетчатого поля

to start

t1, cg

pu setpos [-220 -160] seth 0

pd

repeat 2[fd 320 rt 90 fd 440 rt 90]

pu

rt 45 fd 10 setc 45 fill

setc 9 bk 10 lt 45

; Нарисовали желтый прямоугольник

pd

repeat 5 [setx xcor + 40 sety 160 setx xcor + 40 sety -160]

setx xcor + 40 sety 160 sety -160

; Построили вертикальную сетку

repeat 4[sety ycor + 40 setx -220 sety ycor + 40 setx 220]

;Построили горизонтальную сетку

pu setpos [-220 -160]

freezebg ; Заморозили фон

 

; Дополняем среду кнопками вызова процедур

newbutton "b1 [-360 210] [cg]

set "b1 "надпись "Очистка

set "b1 "размер [100 25]

 

newbutton "b2 [-260 210] [task1]

set "b2 "надпись "Задача_1

set "b2 "размер [100 25]

 

newbutton "b3 [-160 210] [task2]

set "b3 "надпись "Задача_2

set "b3 "размер [100 25]

 

newbutton "b4 [-60 210] [task3]

set "b4 "надпись "Задача_3

set "b4 "размер [100 25]

 

newbutton "b5 [40 210] [task4]

set "b5 "надпись "Задача_4

set "b5 "размер [100 25]

 

newbutton "b6 [140 210] [task5]

set "b6 "надпись "Задача_5

set "b6 "размер [100 25]

 

newbutton "b7 [240 210] [task6]

set "b7 "надпись "Задача_6

set "b7 "размер [100 25]

end

Построение среды задач

to task1

; ==================

; Простейшая задача - дойти и вернуться

; ==================

t1, cg

pu setpos [0 -140]

setc 15 fill setc 9

sety -100 + 40 * random 7

seth 180

setc 105 fill setc 9

end

 

to task2

;============

;Лесенка

;============

t1, cg

pu

setpos [-200 -140] setc 15 seth 0 fill

repeat 6[setx xcor + 40 sety ycor + 40 fill]

setc 65 sety ycor + 40 fill setc 9

sety -100 + 40 * random 6

setx ycor - 100

setc 105 fill setc 9

end

to task3

;=====================

; Коридор

;=====================

t1, cg pu

setpos [-200 -140] setc 15 fill

repeat 7[setx xcor + 40 sety ycor + 40 fill]

setpos [-80 -140] setc 15 fill

repeat 7[setx xcor + 40 sety ycor + 40 fill]

setc 65

repeat 2[setx xcor - 40 fill] setc 9

sety -140 + 40 * random 6

setx ycor - 20 setc 105 fill setc 9

end

to task4

;=====================

; Горка

;=====================

t1, cg pu

setpos [-200 -140] setc 15 fill

repeat 5[setx xcor + 40 sety ycor + 40 fill]

setc 65 sety ycor + 40 fill

sety ycor - 40

setc 15

repeat 5[setx xcor + 40 sety ycor - 40 fill]

sety -100 + 40 * random 4

setx ycor - 100

setc 105 fill setc 9

end

Решение задач "Рекурсия на клетчатом поле"

to zadacha1

; ==================

; Простейшая задача – только дойти

; ==================

fd 40 wait 1

if colorunder = 15 [

setc 45 fill setc 9 stop]

zadacha1

end

to zadacha1_1

; ==================

; Дойти и вернуться

; ==================

fd 40

if colorunder = 15 [

setc 45 fill setc 9 bk 40 stop]

zadacha1_1

bk 40

end

to zadacha2

;============

;Лесенка

;============

step_up

if colorunder = 65 [setc 45 fill setc 9

step_down stop]

zadacha2

step_down

end

to step_up

fd 40 rt 90 fd 40 lt 90

end

to step_down

rt 90 bk 40 lt 90 bk 40

end

to zadacha3

;=====================

; Коридор

;=====================

step1

if colorunder = 65 [

setc 45 fill

setx xcor + 40 fill

setx xcor - 40 setc 9

step2 stop]

zadacha3

step2

end

to step1

setx xcor + 40 sety ycor + 40

end

 

to step2

sety ycor - 40 setx xcor - 40

end

to zadacha4

;=====================

; Горка

;=====================

step_up1

if colorunder = 65 [

setc 45 fill setc 9

step_down1 stop]

zadacha4

step_down1

end

to step_up1

sety ycor + 40

setx xcor + 40

end

to step_down1

setx xcor + 40

sety ycor - 40

end

Литература

1. Сопрунов С.Ф. Лого: программирование для учения. // Информатика, № 23/2007.

2. Волкова Р.А. Программирование в среде ЛогоМиры, часть 6: программирование списков. / Компьютерные инструменты в образовании, № 6/2004.

3. Harvey B. Computer Science Logo Style 2/e — 3 vol. set, MIT Press, 1997, vol 1, pp. 131–147.

4. Кузнецова И.Н. Моделирование в среде Лого. Занятие 3. Работа с переменными // Компьютерные инструменты в образовании. СПб.: Изд-во ЦПО “Информатизация образования”, № 9/2004.