Раздел программы:

«Алгоритмизация и программирование»

Тип урока:

комбинированный урок

Цели:

• Углубить представления учащихся о методах использования операторов ветвления и цикла;
• Формирование представлений о рекурсии и возможностях ее использования;
• Формирование навыков составления алгоритмов, содержащих рекуррентные формулы;

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

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

Задачи:

• Закрепить, обобщить знания учащихся по данной теме;
• Ввести понятия: рекурсия, рекуррентная формула, граничное условие;
• Познакомить учащихся с основными приемами составления алгоритмов, содержащих рекуррентные формулы;
• Закрепление навыков работы с операторами ветвления и цикла;
• Выполнение учащимися упражнений и практических заданий.

Этапы урока:                                                    Время

1. Организационный момент.                              1     
2. Постановка целей и задач урока.                    3
3. Актуализация знаний                                       7
4. Изложение нового материала                          8
5. Самостоятельная работа учащихся                  10
6. Самопроверка                                                    5
7. Итоги урока.                                                      3
8.  Домашнее задание.                                           3

                                                                                               
Ход урока

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

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

1. Цели, план урока, мотивация

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

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

Почему именно рекурсия?

Действительно, почему именно рекурсии посвящен наш сегодняшний урок? Разве это не рядовой прием программирования, один из многих?

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

• Прежде всего, рекурсия красива. Изящество рекурсии в программировании можно сравнить только с изяществом метода индукции в математике.
• Многие структуры, как искусственного, так и естественного происхождения, рекурсивны по самой своей сути. Рассмотрите ветви и корни деревьев, структуру сложной организации, иерархию классов в сложной программе, фракталы – в любой из этих структур вы найдете многочисленные повторения целого в части. Таким образом, многие сущности естественным образом могут быть смоделированы рекурсивными структурами. А чем же еще обрабатывать рекурсивную структуру, как не рекурсивной процедурой?
• Немало задач имеет также рекурсивную природу. Даже, пожалуй, большинство нетривиальных задач. По крайней мере, в программировании далеко не нов метод декомпозиции задачи на несколько более простых, те, в свою очередь, разделяются на еще более простые, и так до тех пор, пока не дойдем до элементарных частей, решить которые достаточно просто. Естественно, программисты не являются монополистами в этой области: подобными методами пользуются архитекторы, машиностроители, математики…

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

В задачах, которые мы рассмотрим на сегодняшнем уроке, нам встретятся операторы ветвления и цикла. Давайте вспомним их основные свойства.

1. Определите значение переменной S после выполнения следующих операторов:

s:=0; n:= 5;

for i:=2 to n do s:= s+100 div i;

s:=0; i:=1;

repeat s:=s+5 div i; i:= i-1; until i<=1;

1. Какие из приведенных операторов правильные и почему?

for i:=20 to 10 do if a mod 3 = 0 then d:=d+1;

for i:=30 downto 20 do begin d:= d+1; i:= i-1 end;

i:=1;

while i <=10 do i :=i-1;

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

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

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

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

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

 n!=1∙2∙3∙...∙n.
то есть представляет собой произведение натуральных чисел от 1 до n включительно.

С другой стороны,

n!=1, если n<=1

n= n*(n-1)!, если n>1

Граничным условием в данном случае является n<=1.

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

Как же выглядит рекурсия на практике? Попробуем реализовать рекурсивное вычисление факториала на Turbo Pascal:

if n <=1 then factorial:=1
else factorial:=n* factorial(n-1)

Как видим, реализация функции ничем принципиально не отличается от рекурсивного определения факториала.

Рекурсия и итерация: две стороны одной медали. Зачем все это нужно? Ведь первоначальное определение факториала ничуть не хуже, выглядит гораздо привычнее, да и реализовать его, в общем-то, не сложнее:
 

f:=1;
for i:=1 to n do
f:=f*i;

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

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

Пример2

  Числа Фиббоначи

Механизм рекурсии часто объясняют на вычислениях чисел Фибоначчи, первые 10 которых приведены в таблице:

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

Эти числа могут быть определены следующим соотношением:

Если для факториала, на первый взгляд, рекурсивное определение выглядит сложнее, чем итеративное, то для чисел Фиббоначи рекурсивное определение выглядит для вычисления лучше, чем прямая формула.

Т.к. с процедурами и функциями вы еще не знакомы, поэтому мы рассмотрим программы, содержащие рекуррентные соотношения.

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

Рекуррентными называются соотношения, в которых новые значения переменных последовательно определяются по предыдущим значениям в соответствии с заданным рекуррентными формулами (от позднелатинского recursio — возвращение, родительный падеж recurrentis - возвращающийся),

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

Рекуррентные формулы          Начальные значения

i = i + 1                                                  2

f_i = f_i-2 + f_i-1                                            f₀ = 1, f₁ =1

_________________           

i <= n

Как же выглядит рекурсия на практике? Попробуем реализовать рекурсивное вычисление n-го числа Фиббоначи на Turbo Pascal:

program fibbonachi;

var i, n: byte; r, t, f: integer;;  {r, t – два предыдущих числа}

begin

writeln (‘введите неотрицательное значение n’);

read (n);

if n <= 1 then f := 1

else begin r:=1; t:=1;

for i:=2 to n do begin

                                   f:= r + t;

r:=t; t:=f

                                         end

                             end;

write (f:5);

end.

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

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

Продолжение, задания для самостоятельной работы - в прикрепленном файле