Конспект урока по теме: "Рекурсия и рекурсивные алгоритмы в ЯП Паскаль"

Тема урока: «Рекурсия и рекурсивные алгоритмы в ЯП Паскаль» Цели и задачи урока: — образовательная  сформировать у учащихся единую систему понятий, связанных с понятием  рекурсии;  научить применять рекурсивные алгоритмы при решении задач на ЯП Паскаль;  показать основные приемы использования рекурсии; — воспитательная  воспитать аккуратность, внимание, организованность;  культура вычислительных навыков; — развивающая  развить логическое мышление, алгоритмического мышления учащихся;  развить знания и умения составлять и отлаживать подпрограммы на языке  Паскаль. Оборудование: ПК, проектор, экран, презентация «Рекурсия в ЯП Паскаль» Тип урока: урок изучения нового материала Этапы урока:  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