Тема урока: Рекурсия. Разработка программ с использованием рекурсивных функций

Тема урока: Рекурсия. Разработка программ с использованием рекурсивных функций.

Цель Д: ввести понятие рекурсии

Р:

В:

Тип урока:

Ход уроку

I.  Организационный момент

II.  Проверка домашнего задания

III.  Новая тема

Программы могут содержать вызов одной или нескольких подпрограмм. Подпрограммы могут, в свою очередь, вызывать другие подпрограммы.

Может ли подпрограмма вызывать саму себя?

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

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

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

Вычисление факториала числа:

n!=1*2*3*…*n

1)  Обычный способ:

Fact:=1; for i:=1 to n do Fact=Fact * і ;

2)  Рекурсивный способ:

n!= 1, при n=0 (0!=1,1!=1по определению) ;

(n-1)!* n, при n>0.

Текст функции:

Function Fact( n : integer) : integer;

begin

If n=0 then Fact:=1 else Fact:= Fact(n-1) * n

end;

Вычисление степени с натуральним показателем хк

1) Обычный способ:

р:=1; for i:=1 to к do р=р*х ;

2)Рекурсивный способ:

1, при к = 0;

Хк=

хк-1, при к > 0.

Function Power( k : integer; x : real) : integer;

begin

If k=0 then Power:=1

else Power:=Power(k-1, x) * х

end;

Преимущества использования рекурсии:

рекурсивный алгоритм более короткий и более наглядный.

Недостатки:

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

Вычисление 15-го числа Фибоначчи
Fk= Fk-1+ Fk-2 (рекурсивный способ)

Внимание!

При вычислении 31-го числа Фибоначчи рекурсивным способом компьютер выполнит >1 млн. операций добавления, 45-го > 1 млрд.!!! (что может привести к переполнению стеку). Для сравнения: вычисление по обычному способу нуждается в 31 и 45 операций добавления соответственно!

Решение задач.

а)Program recursia;

Var

x, a,d:integer;

Function rec(n, a1:integer):integer;

Begin

if n=1 then rec:=a1 else rec:=rec(n-1,a1)+d

End;

Begin

Writeln('vvod chisla x, a,d');

Readln(x, a,d);

Writeln(rec(x, a));

readln;

End.

IV.  Подведение итогов урока

V.  Постановка домашнего задания

а)Program recursia;

Var

x:integer;

Function rec(n:integer):integer;

Begin

if n=0 then rec:=0 else

rec:=rec(n div 10)+n mod 10

End;

Begin

Writeln('vvod chisla x');

Readln(x);

Writeln(rec(x));

readln;

End.

б)Program recursia;

Var

x:integer;

Function rec(n:integer):integer;

Begin

if n=0 then rec:=0 else

rec:=rec(n div 10)+1

End;

Begin

Writeln('vvod chisla x');

Readln(x);

Writeln(rec(x));

readln;

End.