Использование рекурсивных процедур

Тема: «Использование рекурсивных процедур»

Цель:

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

Развивающая. Развивать алгоритмическое мышление, познавательные интересы, навыки работы на компьютере.

Воспитательная. Продолжить формирование коммуникативной культуры, информационной культуры, внимательности, аккуратности, дисциплинированности.

Тип урока: изучение нового материала

Форма урока: синтетическая.

Место урока в учебной теме: первичный

Методы и методические приемы:

1 Информационно - рецептивный:
а) словесный: рассказ - объяснение, описание, беседа,

б) наглядный: иллюстрации, демонстрация, ТСО.
Приемы обучения: изложение информации, объяснение, активизация внимания и мышления, получение из текста и иллюстраций новых знаний, работа с раздаточным материалом.
2. Репродуктивный.
Приемы обучения: подача материала в готовом виде, конкретизация и закрепление уже приобретенных знаний.
3. Визуальный: составление логических цепочек.
4. Суггестивный: применение различных видов искусства.

5. Перцептивный (восприятие и связь с жизнью):
6. Релаксопедический: психологическая разгрузка.
Межпредметные связи: математика, экономика

Материалы и оборудование: флипчарт, проектор, ноутбук

Основные понятия и термины: процедура, рекурсия

Ход урока

1. Организационный момент

2. Актуализация знаний

Фронтальный опрос

1. Что такое ветвление? Приведите примеры.

2. Как написать ветвление в программе ГРИС?

3. Какие виды ветвления вы знаете?

1. Изучение нового материала

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

Рекурсивной называется процедура, в которой имеется обращение к самой к себе.

Не все исполнители могут использовать рекурсии. Такая возможность имеется в «Стрелочка». При программировании некоторых задач рекурсия может служить альтернативой циклу.

Пример: начальное положение «Стрелочка» - произвольная точка в первой строке рабочего поля, направление «вправо». Требуется построить линию, идущую из этой точки до правой границы области.

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

Алгоритм Путь 1_0

Дано: исполнитель в точке А

Надо: воспроизвести образец

нач

пока впереди не стена

нц

шаг

кц

кон

А теперь воспользуемся рекурсией, для чего опишем процедуру ЛИНИЯ_1

Алгоритм Путь 1_1

Дано: исполнитель в точке А

Надо: воспроизвести образец

нач

делай ЛИНИЯ_1

кон

процедура ЛИНИЯ_1

шаг

делай ЛИНИЯ_1

конец процедуры

В теле этой процедуры присутствует команда обращения к самой себе: делай Линия_1.

Пошаговое исполнение (трассировка) такой программы:

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

Алгоритм Путь 1_2

Дано: исполнитель в точке А

Надо: воспроизвести образец

нач

делай ЛИНИЯ_2

кон

процедура ЛИНИЯ_2

если впереди НЕ стена

то

шаг

делай ЛИНИЯ_2

все

конец процедуры

Пошаговое исполнение (трассировка) такой программы:

Поскольку в описании алгоритма присутствует «точка остановки», исполнитель, дойдя до стены остановится.

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

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

Алгоритм Путь_2

Дано: исполнитель в точке А

Надо: воспроизвести образец

нач

делай ЛИНИЯ_3

кон

процедура ЛИНИЯ_3

если впереди НЕ стена

то

шаг

делай ЛИНИЯ_3

прыжок

иначе

поворот

поворот

все

конец процедуры

Пошаговое исполнение (трассировка) такой программы:

Если при выполнении процедуры происходит рекурсивное обращение к ней самой, то это значит, что не произошёл выход из этой процедуры при предыдущем обращении. Этот выход откладывается на будущее. Затем, после окончания рекурсивных обращений, все отложенные выходы обрабатываются в порядке, обратном порядку рекурсивных обращений. В данной программе обработка отложенных выходов начинается с выполнения команды поворот.

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

1. Систематизация полученных знаний

Алгоритм Фигура

Дано: исполнитель в точке А

Надо: воспроизвести образец

нач

делай ЛИНИЯ

поворот

поворот

поворот

шаг

шаг

кон

процедура ЛИНИЯ

если впереди НЕ стена

то

шаг

делай ЛИНИЯ

шаг

иначе

поворот

поворот

поворот

шаг

шаг

поворот

поворот

поворот

все

конец процедуры

1. Итог урока

1. Что нового вы узнали сегодня на уроке?

2. Где еще можно применять полученные знания?

1. Домашнее задание

§ 1.2. стр. 50 – 58 задание 3,4 стр. 56

подготовка к контрольной работе