Цели урока:
образовательная: сформировать понятия рекурсивного объекта и рекурсивного определения, познакомить учащихся с рекурсивными алгоритмами, научить ребят составлять программы с использованием рекурсивных функций;
выражений на алгоритмический язык;
развивающая: развивать логическое мышление;
воспитательная: воспитывать интерес к предмету
Ход урока.
I. Орг. момент.
II. Повторение.
Структура программы; процедуры ввода-вывода; оператор присваивания; типы данных; операции; операнды; подпрограммы, параметры.
III. Закрепление материала.
Объект, частично состоящий или определяющийся с помощью самого себя, называется рекурсивным объектом.
Рекурсивные объекты обладают несколькими свойствами:
- простотой построения;
- несхожестью конечного результата с начальными данными;
- внутренним самоподобием.
Рекурсивным определением называется определение, которое задает некоторый объект в терминах более простого случая этого же объекта.
Как и цикл, рекурсивное определение содержит повторения, но каждый раз при этом используются новые данные (повторения не являются явными).
Рекурсия - это способ описания функций или процессов через самих себя.
Описание процессов осуществляется с помощью алгоритмов.
2 этапа выполнения рекурсивных алгоритмов:
1) "погружение" алгоритма в себя, т. е. применение определения "в обратную сторону", пока не будет найдено начальное определение, не являющееся рекурсивным;
2) последовательное построение от начального определения до определения с введенным в алгоритм значением.
Примеры рекурсивных алгоритмов, оформленных в виде процедур и функций.
1) Вычисление факториала - n!
2) Вычисление степени с натуральным показателем.
program stepen;
var y:real; n:integer;
function power(k:integer; x:real):real;
begin
if k=0 then power:=1 else power:=x*power(k-1,x);
end;
begin
writeln('Введите основание степени: x=');
readln (y);
writeln('Введите показатель степени: k=');
readln (n);
writeln ('x в степени k', power(n,y));
end.
3) Вычисление чисел Фибоначчи по формуле: F(k)=F(k-1) + F(k-2).
4) Решение задачи о Ханойских башнях.
Домашнее задание: выучить все определения + задача
Определить рекурсивно умножение как сложение и деление как вычитание и оформить алгоритмы в виде рекурсивных функций с вызовом из главных программ.