Рекурсия « Я оглянулся посмотреть, не оглянулась ли она, чтоб посмотреть, не оглянулся ли я...» М. Леонидов. - презентация

1 Рекурсия « Я оглянулся посмотреть, не оглянулась ли она, чтоб посмотреть, не оглянулся ли я...» М. Леонидов

2 Примеры рекурсий Матрешка Зеркало в зеркале Телевизор в телевизоре Задача о Ханойских башнях Лингвистические рекурсии: 1.У попа была собака… 2.Дом, который построил Джек… (Р. Бернс)

3

4 Рекурсивной называют процедуру или функцию, внутри которой происходит обращение самой к себе, но с другими параметрами. Это прямая рекурсия.

5 Косвенной называется рекурсия, когда две или более процедуры или функции вызывают друг друга. Пример косвенного вызова процедуры или функции: процедура A вызывает процедуру B, а процедура B вызывает процедуру A

6 Структура описания рекурсивных процедур (функций) имеет следующий вид: ; if then else

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

8 Механизм работы рекурсии 1.Со входом в рекурсию осуществляется вызов процедур (функций), а для выхода необходимо помнить, откуда пришли, т.е помнить точки возврата (адреса). 2. Место хранения точек возврата называется стеком вызова и для него отводится определенная область оперативной памяти.

9 Механизм работы рекурсии 3. В стеке запоминаются также значения всех локальных переменных, т.е. создается копия параметров процедур (функций). 4. Стек ограничен! Возможно его переполнение – это главный недостаток рекурсии!

10 Вычисление факториала N! 0!=1!=1 2!=2=1!*2=1*2 3!=2!*3=1!*2*3=1*2*3 /……………………….. N!= 1*2*3*4*….*n function fact(n:byte):longint; begin If (n=0)or (n=1) then fact:=1 else fact:=fact(n-1)*n; end;

11 Работа рекурсивной функции для n=3 1. n=3 Fuction fact(3); begin fact:=3*fact(2); end; 2. n=2 Fuction fact(2); begin fact:=2*fact(1); end; 3. n=1 Fuction fact(1); begin fact:=1; end;

12 Процедура ввода с клавиатуры последовательности чисел (окончание ввода - 0) и вывода ее на экран в обратном порядке. procedure solve; var n:integer; begin readln(n); if n0 then solve; write (n:5); end;

13 Работа рекурсивной функции для n=3 1. n=3 procedure solve; var n:integer; begin readln(3); if 30 then solve; write (n:5); end; 2. n=2 procedure solve; var n:integer; begin readln(2); if 20 then solve; write (n:5); end; 3. n=0 procedure solve; var n:integer; begin readln(0); {if 00 then solve;} write (n:5); end;

14 Поиск n-ного числа Фибоначи (1,1,2,3,5,8,….) Function fib (n:integer):integer; begin If n

15 Работа рекурсивной функции для n=3 1. n=3 Function fib (3); begin If 3

16 Найти сумму n членов арифметической прогрессии(первый член – а, разность – d) Function sa (n,a:integer):integer; begin If n>0 then sa:=a+sa(n-1,a+d) else sa:=0; End;

17 Работа рекурсивной функции для n=3 1. n=3 Function sa(3,a); begin If 3>0 then sa:=a+sa(2,a+d); End; 2. n=2 Function sa (2,a+d); begin If 2>0 then sa:=(a+d)+sa(1,a+2*d); End; 3. n=1 Function sa (1,a+2*d); begin If 1>0 then sa:=(a+2*d)+sa(0,a+d); End; 4. n=0 Function sa (0,a+d); begin sa:=0; End;

18 Процедура, определяющая минимум среди элементов массива а a- глобальная переменная; n – размерность массива; если n>=2, то минимум среди a[n] и минимума из первых n-1 элементов массива если n=1, то минимум равен a[1]

19 Procedure a_min(n:integer; var x:integer); begin if n=1 then x:=a[1] else begin a_min(n-1,x); if a[n]

20 Работа процедуры для массива из 4-х чисел с элементами 3,1,-2,4 Прямой порядок a_min(4,x); n1 a_min(3,x); n1 a_min(2,x); n1 a_min(1,x); n=1; x:=a[1]=3; Обратный порядок n=2; a[2]

21 Домашнее задание: Для приведенных примеров прорисуйте схемы работы процедур (функций) для конкретных входных данных (не очень больших!, иначе глубина рекурсии будет очень большой) Найти максимальный элемент в глобальном одномерном массиве А.

22 Функция подсчета в строке суммы цифр function f(s:string):integer; var x,c,k:integer; begin n:=length(s); if n=0 then f:=0 else begin val(s[n],x,c); k:=0; if c=0 then k:=x; s:=copy(s,1,n-1); f:=f(s)+k end;

23 Процедура удаления из строки всех точек procedure f(s:string); begin if length(s)>0 then begin s:=copy(s,1,length(s)-1); f(s) end; if s[length(s)]'.' then write(s[length(s)]); end;

24 Фракталом называется множество, части которого являются повторением образа самого множества.

25 В данном рисунке 2 уровня, на каждом из которых большая окружность окружена четырьмя окружностями поменьше, каждая из меньших в свою очередь окружена еще меньшими окружностями и т.д. Алгоритм построения будет заключаться в следующем: Написать процедуру изображения одной окружности с четырьмя окружностями поменьше Использовать эту процедуру с другими параметрами для построения окружностей следующего уровня

26 Для построения каждого уровня необходимо знать расстояние от центра большой окружности до малой и радиус малой окружности. rm, rб, ro - радиус малой окружности, радиус большой окружности и радиус орбиты (т.е. расстояние от центра большой окружности до малой) соответственно. k1= rm / rб, k2= ro / rб. Задав значения k1, k2 можно на каждом уровне вычислять расстояние от центра большой окружности до малой и радиус малой окружности. Формальными параметрами процедуры являются: х, у - координаты центра большой окружности данного уровня, г - радиус большой окружности данного уровня, г1 - радиус орбиты, n - номер уровня. При каждом вызове процедуры номер уровня уменьшается на 1 и выход из рекурсии осуществляется при n=0.

27 uses graph; var x, y, n, r, r1, gd, gm: integer; k1,k2:real; procedure picture2(x,y,r,r1,n:integer); var x1,y1, i: integer; begin if n>0 then begin circle(x,y,r); r1:=trunc(r*k2); for i:=1 to 4 do begin x1 :=trunc(x+r1 *cos(pi/2*i)); y1 :=trunc(y+r1 *sin(pi/2*i)); picture2(x1,y1, trunc(r*k1),r1,n-1); end; begin x:=300; y:=200; k1:=0.3; k2:=2; readln(n); readln(r); Gd :=detect; InitGraph(Gd, Gm, ); picture2(x,y,r,r1,n); Readln; closegraph; end.

28 Написать программу построения следующего изображения: В треугольнике проведены три средние линии. В результате он разбивается на 4 новых треугольника. В каждом треугольнике, кроме центрального, опять проводятся средние линии и т.д.

29 uses graph; var xa, xb, xc, ya, yb, yc, n, gd, gm,r: integer; procedure triangle (xa,ya,xb,yb,xc,yc,n: integer); var xp, xq, xr, yp, yq, yr: integer; begin if n>0 then begin {высчитываются координаты средних линий треугольников} xp:=(xb+xc) div 2; yp:=(yb+yc) div 2; xq:=(xa+xc) div 2; yq:=(ya+yc) div 2; xr:=(xb+xa) div 2; yr:=(yb+ya) div 2; {рисуем средние линии треугольника} line(xp,yp,xq,yq); line(xq,yq,xr,yr); line(xp,yp,xr,yr); {рекурсивно вызываем алгоритм для новых треугольников} triangle(xa,ya,xr,yr,xq,yq,n-1); triangle(xb,yb,xp,yp,xr,yr,n-1); triangle(xc,yc,xq,yq,xp,yp,n-1); end;

30 begin xc;=300; yc:=0; xb:=600; yb:=400; xa:=0; ya:=400; readln(n); Gd := Detect; lnitGraph(Gd, Grn, ); line(xa,ya,xb,yb); line(xb,yb,xc,yc); line(xa,ya,xc,yc); triangle(xa,ya,xb,yb,xc,yc,n); readln; closegraph; end.

31 Дан линейный массив чисел, записать его в обратном порядке. var A:array [1..10] of integer; procedure invertItem(N1, M1:integer); begin t := A[N1]; A[N1] := A[M1] A[M1] := t inc(N1); dec(M1); if N1 < M1 then invertItem(N1, M1) end; invertItem(1, 10);

32 Дан массив, напишите рекурсивную программу для вычисления суммы 1/a[i] function summa(n: integer): real; var S: real; begin if n = 0 then summa:=0 else begin S:=summa(n-1); summa:=S+1/a[n]; end; end; Или function s(r:integer):integer; begin inc(i); if i

33 алгоритм вычисления суммы элементов массива function Summa(k:byte;x:Mas):integer; begin if k=0 then Summa:=0 else Summa:=x[k]+Summa(k-1,x) {если массив пуст, сумма=0, иначе к предыдущей сумме добавляем значение текущего элемента} end;