Урок № 14 Тема: урока: «Рекурсия и рекурсивные алгоритмы в ЯП Паскаль»

Цели и задачи урока:

·         образовательная

·         сформировать у учащихся единую систему понятий, связанных с понятием рекурсии;

·         научить применять рекурсивные алгоритмы при решении задач на ЯП Паскаль;

·         показать основные приемы использования рекурсии;

·         воспитательная

·         воспитать аккуратность, внимание, организованность;

·         культура вычислительных навыков;

·         развивающая

·         развить логическое мышление, алгоритмического мышления учащихся;

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

Оборудование: ПК, проектор, экран, презентация «Рекурсия в ЯП Паскаль»

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

Этапы урока:

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.    Подведение итогов и задание на дом – написать программу возведения числа в квадрат, используя соотношение n²= (n-1)²+2n-1