Цели и задачи урока:
·
образовательная
·
сформировать у учащихся единую систему понятий, связанных с понятием
рекурсии;
·
научить применять рекурсивные алгоритмы при решении задач на ЯП Паскаль;
·
показать основные приемы использования рекурсии;
·
воспитательная
·
воспитать аккуратность, внимание, организованность;
·
культура вычислительных навыков;
·
развивающая
·
развить логическое мышление, алгоритмического мышления учащихся;
·
развить знания и умения составлять и отлаживать подпрограммы на языке
Паскаль.
Оборудование: ПК, проектор, экран, презентация «Рекурсия в ЯП Паскаль»
Тип урока: урок изучения нового материала
Этапы урока:
1.
Организационный момент
2.
Актуализация знаний
3.
Изложение нового материала
4.
Закрепление изученного
5.
Подведение итогов и задание на дом
Ход урока:
1.
Организационный момент
2.
Актуализация знаний – беседа с учащимися
3.
Изложение нового материала
Подпрограммы в Паскале могут обращаться сами к себе. Такое обращение
называется рекурсией. Для того чтобы такое обращение не было бесконечным,
в тексте подпрограммы должно быть условие, по достижению которого дальнейшее
обращение к подпрограмме не происходит.
Пример.
Рассмотрим математическую головоломку из книги Ж. Арсака
«Программирование игр и головоломок». Построим последовательность чисел
следующим образом: возьмем целое число i>1. Следующий член
последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если
i=1, то последовательность останавливается.
Математически конечность последовательности независимо от начального i не
доказана, но на практике последовательность останавливается всегда.
Применение рекурсии позволило решить задачу без использования циклов, как в
основной программе, так и в процедуре.
Пример программы с использованием рекурсии
Program Arsac;
Var first: word;
Procedure posledov (i:
word);
Begin
Writeln (i);
If i=1 then exit;
If odd(i) then posledov(3*i+1) else posledov(i div 2);
End;
Begin
Write (‘ введите первое значение ’); readln (first);
Posledov (first);
Readln ;
End.
Программист разрабатывает программу, сводя исходную задачу к более простым.
Среди этих задач может оказаться и первоначальная, но в упрощенной форме.
Например, для вычисления F( N) может понадобиться
вычислить F( N-1). Иными словами, частью алгоритма вычисления функции будет
вычисление этой же функции.
Алгоритм, который является своей собственной частью, называется рекурсивным. Часто
в основе такого алгоритма лежит рекурсивное определение.
Рассмотрим задачу поиска т-го члена в
последовательности Фибоначчи. Ее можно решить двумя способами – итерационно и
рекурсивно. Построим блок-схему и напишем программу для каждого способа (слайды
6-10). Мы видим, что применив рекурсивный алгоритм,
наша программа стала короче и проще.
4.
Закрепление изученного – беседа с учащимися.
5.
Подведение итогов и задание на дом – написать программу возведения числа в
квадрат, используя соотношение n2= (n-1)2+2n-1