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

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




rene-genon-simvoli-svyashennoj-nauki-stranica-18.html
rene-genon-simvoli-svyashennoj-nauki-stranica-25.html
Тема урока: Рекурсия. Разработка программ с использованием рекурсивных функций.

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

Р: 

В: 

Тип урока: 

Ход уроку



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

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




  1. Новая тема

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

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



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

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

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

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

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


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

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

  1. Рекурсивный способ:

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.


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

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





а)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.




mpedagog.ru