Рекурсия

Цели:

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

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

Воспитательные. Создать условия для воспитания познавательных потребностей, интерес к предмету.познавательных интересов, интеллектуальных и творческих способностей в информационной деятельности, в профильных областях и с применением специализированных профессиональных инструментов;

Ход урока

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

Слайд 1 (Приложение)

а) Записать тему урока. "РЕКУРСИЯ" (RECURCIО - возвращение)

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

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

Учитель: что такое подпрограмма? (Слайд 3).

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

Учитель: что такое формальные и фактические параметры? (Слайд 4).

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

Учитель: что такое функция? (Слайд 5).

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

Учитель: к чему относится описание типа в конце заголовка подпрограммы функции? (Слайд 6).

Ученик: Это описание относится к имени функции, которому необходимо присвоить значение результата.

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

В Паскале возможно применения рекурсии в процедурах и функциях.

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

Что такое рекурсивный объект и каковы его свойства (Слайд 7).

Рассмотрим несколько примеров

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

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

(Слайды 8-16).

Свойства рекурсивных объектов. (Слайд 17).

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

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

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

2. Примеры рекурсивного определения в математике. (Слайд 18 и 19).

1) Определение натурального числа.

а) 1 - натуральное число;

б) число, следующее за натуральным (т.е. больше его на единицу), есть натуральное число.

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

а)а₁=а₀;

б) а_n=а_n-1+d. При а₀=1, d=1 имеем натуральный ряд 1,2,3,...

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

а) а₁=а₀;

б) а_n=а _n-1*q. При а₀=2, q=2 имеем степенной ряд 2,4,8,16,32,...;

4) Факториал a_n=n! (Fасtоr- сомножитель) n!=1*2*3*4*5*б*...*n.

а)а₁=1;

б) а_n=n*а_n-1.

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

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

x₁=x₂=1

x_n=x_n-1+x_n-2 при n > 2  

Каждый элемент ряда Фибоначчи является суммой двух предшествующих элементов, т.е.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55,:

Историческая справка: (Слайд 20).

Леонардо Фибоначчи (Пизанский), годы жизни 1180 - 1250. В "Книге абака> 1202 г. изложил формулы решения квадратного уравнения по образцу аль-Хорезми, в этой книге впервые встречается правило для нахождения суммы членов произвольной арифметической прогрессии. Фибоначчи придумал последовательность (названную в последствии его именем) натуральных чисел

а) если n<3, то x_n=1;

б) x_n=x_n-1+x_n-2, каждый элемент последовательности, начиная с трётьего равен сумме двух предшествующих.

Определение, которое задает некоторый объект в терминах более простого случая этого же объекта, называется рекурсивным определением. (Слайд 21).

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

З. Что такое рекурсия. (Слайд 23).

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

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

1) "погружение" алгоритма в себя, т.е. применениё определения в "обратную сторону", пока не будет найдено начальное определение, не являющееся рекурсивным;

2) последовательное построение от начального определения до: определения с введенным в алгоритм значением.

4. Примеры рекурсивных алгоритмов. (Слайд 24).

Оформление подпрограмм практически соответствует математическому определению рекурсивной функции.

Вычисление факториала. Программа Faktor1 не рекурсивное вычисление,

Program Faktor1;

Var N:integer;

Function f1(k:integer):real;

Var I:integer; X:real;

Begin

X:=1;

For I:=1 to k do

X:=X*I;

f1:=X

end;

Begin

Write('N=');

Readln(N);

Writeln(f1(N))

End.

Рассмотрим функцию для вычисления факториала с использованием рекурсивной функции:

Function F(n: integer): longin;

Веgin

If n=1 then F:=1

else:=n*F(n-1)

End;

Рассмотрим последовательность вызовов этой функции для n=5. (Слайд 25).

1 вызов (n=5) у:=F(5), так как n<>1, то управление передается на ветку иначе и функция F:=5*F(4).

2 вызов (n=4) n<>1, то F:=4*F(3).

З вызов (n=З) n<>1, то F:=3*F(2).

4 вызов (n=2) n<>1, то F:=2*F(1)=2*1=2..

Возвращаемся назад поднимаясь вверх по цепочке рекурсивных вызовов. (Слайд 26).

3 вызов (n=3), , то F:=3*F(2)=З*2=6.

2 вызов (n=4) , то F:=4*F(3)=4*6=24.

1 вызов (n=5), то F:=5*F(4)=5*24=120.

Это значение присваивается переменной.

Рекурсия не должна восприниматься как некий программистский трюк. Это скорее некий принцип, метод. Если в программе нужно выполнить что-то повторно, можно действовать двумя способами:

• с помощью последовательного присоединения (или итерации в форме цикла);
• с помощью вложения одной операции в другую (а именно, рекурсий).

Рассмотрим программы вычисления чисел Фибоначчи (Слайд 27).

IV. Ввод и исполнение программы вычисления чисел Фибоначчи.

Вычислить 8-е число.

Сколько раз вызывается функция Fib при n=8?

Ответ:21 раз. (Слайд 27-29).

Вывод. Подпрограммы функции, дёлают программу, более наглядной, но рекурсивный вызов функции иногда существенно замедляет работу программы. (Слайд 30).

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

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

Итог урока. Оценки.