Презентація на тему «Рекурсія»
![Презентація на тему «Рекурсія» - Слайд #1 Презентація на тему «Рекурсія» - Слайд #1](http://cdn.gdz4you.com/files/slides/5b4/3c2e55b31641e3d4cfd7867dd501c5d9.jpeg)
Рекурсія
![Презентація на тему «Рекурсія» - Слайд #2 Презентація на тему «Рекурсія» - Слайд #2](http://cdn.gdz4you.com/files/slides/5b5/6534a8436e907efb0ced99edd8d02435.jpeg)
Програми можуть містити виклик однієї або декількох підпрограм. Підпрограми можуть, в свою чергу, викликати інші підпрограми.
А чи може підпрограма викликати саму себе?
![Презентація на тему «Рекурсія» - Слайд #3 Презентація на тему «Рекурсія» - Слайд #3](http://cdn.gdz4you.com/files/slides/5b6/7792b558ca0c76d24d695582021ac501.jpeg)
Алгоритмічна конструкція, в якій підпрограма викликає сама себе, називається рекурсією.
Рекурсивні алгоритми зазвичай виникають там, де вихідну задачу можна звести до такої ж самої, але з іншими аргументами або в інших обставинах.
![Презентація на тему «Рекурсія» - Слайд #4 Презентація на тему «Рекурсія» - Слайд #4](http://cdn.gdz4you.com/files/slides/5b7/2a93f39020f6d31d33f81a191b048cb1.jpeg)
В житті ми маємо такі випадки, коли будь-яке поняття визначається з використанням того ж самого поняття (рекурсія):
цукерка "Ану-ка отними" має на фантику зображення цукерки, яка має зображення цукерки і так далі;
всім відома російська приказка "У попа была собака…";
луна в горах.
![Презентація на тему «Рекурсія» - Слайд #5 Презентація на тему «Рекурсія» - Слайд #5](http://cdn.gdz4you.com/files/slides/5b8/9c36b930df0e0e8b05d4e1fcb4cdef27.jpeg)
Рекурсія дає змогу записувати циклічні алгоритми без використання команд циклу. Розглянемо приклади запису рекурсивних алгоритмів.
![Презентація на тему «Рекурсія» - Слайд #6 Презентація на тему «Рекурсія» - Слайд #6](http://cdn.gdz4you.com/files/slides/5b9/03201ae30e1239054512737f608b91cf.jpeg)
Обчислення факторіалу числа: 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;
![Презентація на тему «Рекурсія» - Слайд #7 Презентація на тему «Рекурсія» - Слайд #7](http://cdn.gdz4you.com/files/slides/5ba/a48a1b922cbd6d5d08664325afd2b1a2.jpeg)
cтек
Рекурсивний виклик функції
oбчислення n!
локальні дані
![Презентація на тему «Рекурсія» - Слайд #8 Презентація на тему «Рекурсія» - Слайд #8](http://cdn.gdz4you.com/files/slides/5bb/eab1bceaa6c5823d7ed86cfc7a8bd824.jpeg)
cтек
Виконання відкладених викликів функції
![Презентація на тему «Рекурсія» - Слайд #9 Презентація на тему «Рекурсія» - Слайд #9](http://cdn.gdz4you.com/files/slides/5bc/aba49b6369ec3a9497c9c54696f6a3fd.jpeg)
Виконання комп'ютером відкладених викликів функції можливе завдяки використанню стекa. Стек – модель оперативної пам'яті, де дані запам'ятовуються і зберігаються за принципом "перший прийшов – останнім вийшов" (аналогом стеку є ріжок для набоїв у автоматі).
![Презентація на тему «Рекурсія» - Слайд #10 Презентація на тему «Рекурсія» - Слайд #10](http://cdn.gdz4you.com/files/slides/5bd/c05c0c0aa89b97effea59096cad7bd60.jpeg)
Обчислення суми чисел від a до b з кроком 1
1)Звичайний спосіб:
s:=0; for i:=a to b do s:=s+і;
2)Рекурсивний спосіб:
Function Summa (a, b:integer):integer;
begin
If a=b then Summa :=a
else Summa := Summa (a, b-1)+b
еnd;
![Презентація на тему «Рекурсія» - Слайд #11 Презентація на тему «Рекурсія» - Слайд #11](http://cdn.gdz4you.com/files/slides/5be/7a43ed4e82d06a1e6b2e88518fb8c2b0.jpeg)
Обчислення степеня з натуральним показником хк
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;
![Презентація на тему «Рекурсія» - Слайд #12 Презентація на тему «Рекурсія» - Слайд #12](http://cdn.gdz4you.com/files/slides/5bf/8b48a57422b76904b5c3ecde9d4af512.jpeg)
Обчислення чисел ФібоначчіFk= Fk-1 + Fk-2 , F1= F2=1
1)Звичайний спосіб:
x:=1; z:=1; {-перші два числа Фібоначчі }
for i:=1 to k do begin y:=x; x:=z; z:=x+y;
write (z:5) end;
2)Рекурсивний спосіб:
Function Fib (k:integer):integer;
begin
If k<3 then Fib :=1
else Fib := Fib (k-1)+Fib(k-2) end;
![Презентація на тему «Рекурсія» - Слайд #13 Презентація на тему «Рекурсія» - Слайд #13](http://cdn.gdz4you.com/files/slides/5c0/a4267159aa970aa5a6542bcbb7ef575e.jpeg)
Переваги використання рекурсії:
рекурсивний алгоритм коротший і наглядніший.
Недоліки:
обчислення рекурсивного алгоритму на компютері потребує більше часу (за рахунок повторних звертань до підпрограми) і пам'яті (за рахунок дублювання локальних змінних підпрограми).
![Презентація на тему «Рекурсія» - Слайд #14 Презентація на тему «Рекурсія» - Слайд #14](http://cdn.gdz4you.com/files/slides/5c1/2578eb9cdf020730f77793e8b58e165a.jpeg)
Обчислення 15-го числа ФібоначчіFk= Fk-1+ Fk-2 (рекурсивний спосіб)
F15
F14 F13
F13 F12 F12 F11
F12 F11 F13 F12 F11 F10 F10 F9
F11 F10 . . . . . . . . . . . . . . . . . . . . F8 F7
F9 F8 .. . . . . . . . . . . . . . . . F7 F6
![Презентація на тему «Рекурсія» - Слайд #15 Презентація на тему «Рекурсія» - Слайд #15](http://cdn.gdz4you.com/files/slides/5c2/ee88c0f86505bcab820bb84ad06e895e.jpeg)
Увага!
При обчисленні 31-го числа Фібоначчі рекурсивним способом комп'ютер виконає >1 млн. операцій додавання,
45-го > 1 млрд.!!! (що може призвести до переповнення стеку).
Для порівняння:
обчислення за звичайним способом потребує 31 та 45 операцій додавання відповідно!
![Презентація на тему «Рекурсія» - Слайд #16 Презентація на тему «Рекурсія» - Слайд #16](http://cdn.gdz4you.com/files/slides/5c3/e7364a5abd2a860cf8e33b114369b92b.jpeg)
Задача про Ханойські вежі.
Потрібно перекласти диски з осі А на вісь С, користуючись віссю В так, щоб більший диск не класти на менший. За один раз можна перекладати один диск.
А
В
С
![Презентація на тему «Рекурсія» - Слайд #17 Презентація на тему «Рекурсія» - Слайд #17](http://cdn.gdz4you.com/files/slides/5c4/4d171e8c3b2ef70c7afb02614b99e632.jpeg)
Програма
procedure Xanoj(n : integer; A,B,C: char); begin
If n=1 then writeln(‘перекласти диск з осі', A, 'на вісь', C)
else begin
Xanoj(n-1, A, B, C);
writeln(‘перекласти диск з осі', A, 'на вісь', C)
Xanoj(n-1, B, C, A);
end end; {кінець процедури}
Var n: integer ;
begin writeln(‘задайте кількість дисків'); readln(n);
Xanoj(n,'A','B','C') end. {кінець головної програми}
![Презентація на тему «Рекурсія» - Слайд #18 Презентація на тему «Рекурсія» - Слайд #18](http://cdn.gdz4you.com/files/slides/5c5/23f35020df135821bc9a1c51e3900047.jpeg)
A
B
c
Виконання рекурсивної процедури для перекладання трьох дисків
![Презентація на тему «Рекурсія» - Слайд #19 Презентація на тему «Рекурсія» - Слайд #19](http://cdn.gdz4you.com/files/slides/5c6/685d3703a0b1410dc3bf2280eb5a15ec.jpeg)
Дякуємо за увагу!