Образовательная галактика Intel®

Блог Участника

Запись блога

Карандашное программирование: рекурсия

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

Среду http://pencilcode.net/ можно использовать для обучения детей младшего школьного возраста одной из основных концепций программирования - рекурсии. С рекурсией тесно связана математическая индукция, которая изучается в старших классах, а также геометрические фракталы (Треугольник Серпинского, Снежинка Коха, Дерево Пифагора и т.д.).

Цитата
Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. (Википедия)


См. посты на Галактике:
STEAM-проект: снежинка Коха, треугольник Серпинского и другие фрактальные объекты в GeoGebra
Суха теория, мой друг, а древо жизни вечно зеленеет...)


Примеры объектов, созданных при помощи рекурсии в http://pencilcode.net/

Рекурсия. Спираль.
Перед заходом на это упражнение, повторить, как с помощью цикла строится квадрат. В теле цикла, повторяющегося 4 раза, есть две команды: движение вперед и поворот вправо:


Обсудить: как из квадрата сделать квадратную сходящуюся (скручивающуюся) спираль?
Обратимся к еще одному определению рекурсии:
Цитата
Рекурсия - это такая организация алгоритма, при которой процедура обращается к самой себе. Сама процедура называется рекурсивной. Источник.


Каждый раз длина каждого витка спирали уменьшается на определенную величину, зависящую от длины предыдущего витка. Это и значит, что длина витка задается рекурсивно.
Зададим процедуру SPIRAL для этого используем блок для определения новой функции, которую назовемSPIRAL. Она зависит от переменной x, первоначальное значение которой положим равным 20. Бесконечно cходящейся (скручивающейся) у нас спираль быть не может: движение вперед (длина витка) не может быть меньше одного черепашьего шага. Т.е. величина отрезка, на который на каждом проходе продвигается черепашка, должна оставаться положительной.
Это и будет наше условие для процедуры. Пока оно выполнено, процедура выполняется. Как только x становится равным нулю, процедура останавливается.

Тогда при прохождении первого витка спирали черепашка продвинется на 10*x = 200 черепашьих шагов, что соответствует 8-ми клеткам (напомним, что сторона клетки равна 25 черепашьим шагам).
При прохождении второго витка SPIRAL : x-1 Вызывает процедуру SPIRAL и передает ей значение параметра 20-1=19. Черепашка пройдет 10 * (x-1) =190 шагов.
При прохождении третьего витка она пройдет 10 * ((x-1)-1) =180 черепашьих шагов.
И т.д. до тех пор, пока длина прохода остается положительной, т.е. выполняется условие x>0.


Рекурсия. Скручивающаяся спираль.

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

Рекурсия. Раскручивающаяся спираль

Подробнее прочитать, почему так происходит и чем отличается хвостовая рекурсия от вложенной можно здесь:
Рекурсия в алгоритмах Материалы Ольги Тузовой.

Рекурсия. Дерево
Большое дерево можно нарисовать, скомбинировав несколько маленьких деревьев, а маленькие деревья могут быть сделаны из крошечных деревьев.
Создавая функцию дерево с аргументом размер, мы можем сделать дерево из более мелких деревьев.

Дерево

Рекурсия. Треугольник Серпинского

Треугольник Серпинского. Автор Ольга Тузова
Фрактал на правильном шестиугольнике. Автор Ольга Тузова
Фрактал на правильном шестиугольнике. Версия Ирины Афониной
Фрактал на правильном семиугольнике.

Рекурсия. Снежинка


Снежинка

Рекурсия. Закрашенные квадраты
В этих проектах для создания закрашенных квадратов используется команда box.

Количество слоев на представленных рисунках: 2, 3, 5
Квадраты 1
Версия рекурсии с квадратами

А какие еще объекты для рисования с использованием рекурсии мы можем создать?

Полезные ссылки
Рекурсия в алгоритмах Материалы Ольги Тузовой.
Треугольник Серпинского. Материалы Ольги Тузовой


Посты по теме карандашного программирования
Карандашное программирование. Начало
Карандашное программирование: смайломания
Карандашное программирование: чужой код для решения своей задачи...
Карандашное программирование: циклы
Геометрия и карандашное программирование
Карандашное программирование: холст как координатная плоскость
Карандашное программирование: рисуем пейзажи масштабированием
Карандашное программирование: четыре черепашки
Карандашное программирование: несколько черепашек и поворотная симметрия
Карандашное программирование: черепашка рисует паркеты и мозаики
Карандашное программирование: черепашка и оптические иллюзии
О творческих домашних заданиях, или Могут ли все ученики быть успешными?
Программирование для воссоздания картин: математика и искусство вместе
В начале была цифра?
Пляшущие черепашки
Искусство создания снежинки, или Как скоротать зиму...
Карандашное программирование: паркеты и жывёлы
Карандашное программирование: рекурсия
Ёлка в коде. МК
Ёлка в коде. Этап 2. Шарики цветные


Брошюра "Карандашное программирование". Л.Рождественская. Верстка Л.Кравченко

Комментарии

Активный пользователь

  • Группа: Пользователи
  • Сообщений: 82
  • Регистрация: 3.10.2012
  • Из: с.Совхозный
  • Номер участника: 119887
Предупреждение

Благодаря вашим публикациям, я стала фанатом pencilcode biggrin.gif

Активный пользователь

  • Группа: Эксперт портала
  • Сообщений: 113
  • Регистрация: 17.2.2011
  • Из: Тямша
  • Номер участника: 94612
Предупреждение

Красота неземная!

У меня есть пара мальчишек из начальной школы, увлекающихся программированием. Они имеют подготовку в Scratch, теперь показала им pencilcode. С линейными алгоритмами для рисования геометрических фигур мы уже справляемся. Вот теперь думаю: как переходить к циклам, процедурам и рекурсиям. Поймут ли?

Активный пользователь

  • Группа: Эксперт портала
  • Сообщений: 597
  • Регистрация: 29.3.2010
  • Из: Таллинн
  • Номер участника: 84498
Предупреждение

Цитата(natyanikova @ 27.1.2017, 13:39)
Красота неземная!

У меня есть пара мальчишек из начальной школы, увлекающихся программированием. Они имеют подготовку в Scratch, теперь показала им pencilcode. С линейными алгоритмами для рисования геометрических фигур мы уже справляемся. Вот теперь думаю: как переходить к циклам, процедурам и рекурсиям. Поймут ли?


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

Возьмем для примеры "циклы". Конечно, для мотивированных ребят они посильны, даже если ученики из началки. Весь вопрос, как ставить учебную задачу? Если идти от открытой задачи (проблемы), для решения которой им понадобится какой-то из блоков циклов, то здесь хороша идея "упрощения" программы. С циклом можно познакомить через прямую подсказку. Или же через демонстрацию работы линейного алгоритма с повторами и второго - с циклом - "сворачивающим" несколько строк кода в более компактный вид.

Потом они сами научатся другим типам через последовательную серию улучшений проекта, задавая вопрос: "А как сделать так, чтобы....?" Я уже писала, повторюсь, что не знаю лучшего способа знакомиться с циклами, чем рисование мандал. Как здесь. Но есть и другие примеры заданий, которые годятся для первого знакомства с циклом.

С переменными - отдельная история. Тут все очень сильно зависит от содержательной сложности и типа задачи. Переменная-счетчик - это одно, переменная для того, чтобы задать параметры команд - другое, а, например, переменная для описания преобразований на плоскости - это третье. Есть еще 4-ое, 5-ое и т.д...
В началке я бы начала со счетчиков и параметров команд, опять же демонстрируя возможность быстро менять код за счет изменений первоначальных значений переменных. Это только один пример.

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

В наших школах был (да и есть, к сожалению) распространен на всех предметах дедуктивный способ обучения: от теории - к практике. Сначала понятие вводится теоретически, дается классификация и примеры использования. А потом даются типовые задачи применения, что входит в так называемую "отработку понятия". Здесь это точно не сработает! И как можно сейчас идти чисто дедуктивным путем, даже не представляю, особенно, с младшими школьниками....
Только от частного к общему: от частного случая использования - к схеме действия, через последовательность шагов к обобщению понятия.

Активный пользователь

  • Группа: Эксперт портала
  • Сообщений: 597
  • Регистрация: 29.3.2010
  • Из: Таллинн
  • Номер участника: 84498
Предупреждение

Цитата(Евгения Васильева @ 26.1.2017, 16:38)
Благодаря вашим публикациям, я стала фанатом pencilcode biggrin.gif


Это было заметно на МК "Елка в коде". А уже делали с учениками что-то? Не поделитесь?

Активный пользователь

  • Группа: Пользователи
  • Сообщений: 82
  • Регистрация: 3.10.2012
  • Из: с.Совхозный
  • Номер участника: 119887
Предупреждение

Цитата(ljudmillar @ 27.1.2017, 15:16)
Цитата(Евгения Васильева @ 26.1.2017, 16:38)
Благодаря вашим публикациям, я стала фанатом pencilcode biggrin.gif


Это было заметно на МК "Елка в коде". А уже делали с учениками что-то? Не поделитесь?

Я пока тренируюсь на своем ребенке (второклассник). Ему очень нравится) Планирую на будущий год взять в началке кружок, поэтому пока набираю базу и коплю ваши публикации rolleyes.gif

Активный пользователь

  • Группа: Эксперт портала
  • Сообщений: 597
  • Регистрация: 29.3.2010
  • Из: Таллинн
  • Номер участника: 84498
Предупреждение

Сегодня попалась на глаза статья, которую не могу не процитировать в подтверждение того, что до сих преобладающий у нас на всех предметах "дедуктивный способ" обучения не единственный возможный и далеко не идеальный. Он не казался идеальным для некоторых уже давно. Например, для Татьяны Михайловны Великановой еще в 70-е, о которой этот пост.

Цитата
"необходимость организации таких видов деятельности ребенка и таких задач, в которых может быть проявлена самостоятельная, поисковая активность ученика. Традиционно основное время уделяется изучению правил и процедур, роль задач - иллюстративная. Сами задачи - очень искусственно сконструированные модели, где все необходимые данные присутствуют, ничего лишнего нет, и ответ всегда получается "хороший"". В жизни всё иначе, - чего-то не хватает, а что-то лишнее специально отвлекает нас от главного. И, хотя проще решать "примеры", но ведь куда интереснее "еще и "поставить", найти или узнать недостающие данные, отбросить лишние, выбрать необходимые процедуры и их последовательность, суметь все это записать удобным способом..."

Статьи по этой теме

« Апрель 2017 »
ВПВСЧПС
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Последние записи

Мои ссылки в блоге

Последние комментарии

Мое изображение

152 пользователей просматривает
151 гостей
1 участников
0 анонимных участников

Категории

Поиск в блоге


Наверх