Методическая разработка урока информатики в 11 классе "Рекурсивные подпрограммы"

Ход урока

I. Организационный момент (мотивационная беседа).

Учитель: Здравствуйте, ребята! Начнем наш урок. Я надеюсь, что наше

сотрудничество будет плодотворным.

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

II. Повторение изученного (создание ситуации успеха)

Учитель: что такое подпрограмма?

Ученик: подпрограмма - это специальным образом оформленный алгоритм,

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

Учитель: Какие виды подпрограмм существует в языке Паскаль?

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

(PROCEDURE) и функция ( FUNCTION ).

Учитель: что такое формальные и фактические параметры?

Ученик: Формальные - условные обозначения в описании процедуры -

описываются в ее заголовке. Фактические - перечисляются при вызове процедуры

и с ними требуется выполнить процедуру.

Учитель: В каком случае удобно использовать в программе процедуру?

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

получить несколько результатов.

Учитель: В каком случае удобно использовать в программе функцию?

Ученик: Когда в подпрограмме необходимо получить единственный результат.

Учитель: Как происходит вызов подпрограммы?

Ученик: Вызов подпрограммы происходит при каждом употреблении ее имени в

основной программе. При вызове подпрограммы устанавливается взаимно

однозначное соответствие между фактическими и формальными параметрами,

затем начинают выполняться команды, заданные в ней. После выполнения

подпрограммы управление передается следующему оператору основной

программы.

Учитель: Процедура или функция может содержать вызов других процедур или

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

Ученик: Возможные ответы учащихся:

-нет, это замкнутый круг, это приведет к зацикливанию программы.

-да, при правильной организации вызова.

Учитель: Это возможно. Никакого парадокса здесь нет – компьютер лишь

последовательно выполняет встретившиеся ему в программе команды и, если

встречается вызов процедуры, просто начинает выполнять эту процедуру. Без

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

заключается сущность рекурсии.

III. Целеполагание

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

Тема урока: "РЕКУРСИЯ"

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

Что такое рекурсивный объект и каковы его свойства?

Сначала посмотрим небольшой фильм.

В жизни на не раз приходилось сталкиваться с рекурсией.

 Мифология

Уроборос – змей, кусающий свой собственный хвост. Это древний символ

бесконечности Вселенной и времени, круговорота жизни, отождествляемых с

рекурсией.

Классическим примером бесконечной рекурсии являются два поставленные друг

напротив друга зеркала: в них образуются два коридора из затухающих

отражений зеркал.

 Рекурсия вокруг нас…

Пример: Русские матрешки

 Русском фольклоре

 Прием рекурсии в литературе.

Несколько рассказов Станислава Лема посвящены (возможным) казусам

при бесконечной рекурсии. Рассказ из «Кибериады» о разумной машине, которая

обладала достаточным умом и ленью, чтобы для решения поставленной задачи

построить себе подобную, и поручить решение ей (итогом стала бесконечная

рекурсия, когда каждая новая машина строила себе подобную и передавала

задание ей).

Н.В. Гоголь в повести «Портрет» описывает сон художника Черткова,

который, как далее выясняется, оказывается сном третьего уровня рекурсии.

Проснувшись от этого сна (первый раз), Чертков попадает на второй уровень

рекурсии – во второй сон. Проснувшись от второго сна, он попадает в первый сон,

от которого тоже придется проснуться.

 Прием рекурсии в живописи.

Гравюра голландского художника Мориса Эшера «Рисующие руки» - одна из

лучших иллюстраций понятия рекурсии.

Существует специальный раздел графики – фрактальная графика. В основе

которой рекурсивное изображение одного и того же узора в самом себе.

 Прием рекурсии в архитектуре.

Сооружения с элементами фрактала "Треугольник Серпинского" - это Эйфелева

Башня в Париже;

Исторический музей, Москва;

Фрактальность современных архитектурных форм.

 Рекурсия в математике:

Идеи рекурсии известны людям издавна. Рекурсивные определения как мощный

аналитический аппарат используются во многих областях науки, особенно в

математике.

1) Арифметическая прогрессия:

2) Геометрическая прогрессия:

3) Факториал a

4) Числа Фибоначчи.

Мы рассмотрели примеры рекурсивных объектов. Рекурсивным называется

любой объект, который частично определяется через себя. Т.е. объект

определяется в терминах более простого случая этого же объекта.

Свойства рекурсивных объектов.

1. Простота построения;

2. Несхожесть конечного результата с начальными данными;

3. Внутреннее самоподобие.

 Рекурсия в программировании

Рекурсия — это такой способ организации вспомогательного алгоритма

(подпрограммы), при котором эта подпрограмма вызывает сама себя.

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

так и процедуры.

Рекурсивная функция (или процедура) обязательно должна содержать в себе

условие окончания рекурсивности или граничное условие, чтобы не вызвать

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

переполнению стека и возникновению ошибки времени исполнения.

Большая часть всех шуток о рекурсии касается бесконечной рекурсии, в

которой нет условия выхода. «Чтобы понять рекурсию, нужно сначала понять

рекурсию».

VI. Самостоятельная работа учащихся в группах.

 Рекурсивные алгоритмы на ЕГЭ

Задание - Умение исполнить рекурсивный алгоритм

Способ решения: последовательное выполнение операций от начального

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

Задание: Алгоритм вычисления значения функции F(n), где n – натуральное

число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) + n, при n 1

Чему равно значение функции F(5)? В ответе запишите только натуральное число.

Пояснение. Последовательно находим:

F(2) = F(1) + 2 = 3,

F(3) = F(2) + 3 = 6,

F(4) = F(3) + 4 = 10,

F(5) = F(4) +5 = 15.

Ответ: 15

IX. Подведение итогов урока. Рефлексия.

a) Что такое рекурсия?

b) Что такое рекурсивный объект?

c) Свойства рекурсивного объекта?

d) Приведите примеры рекурсивного определения в математике.

e) Что называется глубиной рекурсии?

f) Как выполняется рекурсивный алгоритм?

g) Что такое зацикливание и как его избежать? (условие окончания

рекурсивности)

X. Домашнее задание: п.2.3.1