Рекурсия в ПРОЛОГе Понятие рекурсии Примеры рекурсивных объектов Рекурсивные правила в ПРОЛОГе Примеры рекурсивных правил Вычисление факториала Последовательность. - презентация

1 Рекурсия в ПРОЛОГе Понятие рекурсии Примеры рекурсивных объектов Рекурсивные правила в ПРОЛОГе Примеры рекурсивных правил Вычисление факториала Последовательность Фибоначчи Задача о Ханойских башнях

2 Понятие рекурсии Рекурсия способ организации действий, при котором процесс обращается сам к себе. Рекурсивным называется любой объект, который частично определяется через себя.

3 Рекурсия в художественных образах клип Гравюра голландского художника Мориса Эшера "Рисующие руки"

4 ПРИМЕРЫ РЕКУРСИИ У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: "У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: "У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: …

5 Рекурсия в природе

6 Рекурсия в математике: Треугольник Серпиньского фрактал, один из двумерных аналогов множества Кантора предложенный польским математиком В. Серпиньским в 1915 году. Также известен как «решётка» или «салфетка» Серпиньского.фрактал

7 Рекурсия в математике: Снежинка Коха

8 Рекурсия в математике: Алгебраические фракталы Множество Мандельброта. Алгоритм построения основан на простом итеративном выражении: Z[i+1] = Z[i] * Z[i] + C, где Zi и C - комплексные переменные. Итерации выполняются для каждой стартовой точки C прямоугольной или квадратной области - подмножестве комплексной плоскости.

9 Примеры рекурсивных определений 1. Сумма первых N натуральныхчисел S(N)=1+2+3+…+(N-1)+N S(N)= 2. Степень с натуральным показателем X n = X n-1 *X X n =

10 Рекурсивные правила в ПРОЛОГе Рекурсивное правило Рекурсивная часть (обращение к себе) нерекурсивная часть (остановка рекурсии)

11 Примеры рекурсивных правил: Вычисление факториала n!=1*2*3*...*(n-1)*n. Граничное условие: n=0 % нерекурсивная часть правила : 0! = 1 fact (0, 1):- !. % рекурсивная часть правила: n! = (n-1)!*n fact (N, FN):- M=N–1, fact (M, FM), FN=FM*N. n!=

12 fact (0, 1):- !. fact (N, FN):- M=N–1, fact (M, FM), FN=FM*N. fact (3, FN) N=3 FN= M=N =3 -1 fact (2, FM) M=2 FM= FN=FM*N M=M =2 -1 fact (1, FM) M = 1 FM= FM=FM*M M=M =1 -1 fact (0, FM) M=0 FM= 1 FM=FM*M FM=1*1=1 6 FN=2*3=6 FM=1*2=2 1 2

13 Примеры рекурсивных правил: Числа Фибоначчи F(1)=1, Ff(2)=1, F(n)=F(n-1)+F(n-2). 1, 1, 2, 3, 5, 8, 13, 21,... F(n) =

14 Правило для вычисления n-го числа Фибоначчи fib(N,F), N-порядковый номер, F- значение N-го числа Фибоначчи fib(1,1):-!. %F(1) =1 fib(2,1):-!. %F(2) =1 fib(N,F):- %F(N)=F(N-1)+F(N-2) N1=N-1,fib(N1,F1), N2=N-2,fib(N2,F2), F=F1+F2.

15 Задача о Ханойских башнях (1)А В: Разложение исходной задачи на подзадачи: (1) Переложить 1,2-й диски с А на В (АВ) (2) Переложить 3-й диск с А на С (АС) (3) Переложить 1,2-й диски с В на С (ВС) (3)B C: CВCВАСАВ BABCАCАC A A A B B B C C C Решение подзадач: 1,2 Решение при N=3

16 Рекурсивное правило для N дисков move(1,A,B,C):- write("Перенести диск с ", A, " на ",C),nl,!. move(N,A,B,C):- M=N-1,move(M,A,C,B), write("Перенести диск с ", A," на ",C),nl, move(M,B,A,C).

17 Задача о Ханойских башнях АВС Перенести диск с A на B Перенести диск с A на C Перенести диск с B на C Перенести диск с A на B Перенести диск с C на A Перенести диск с C на B Перенести диск с A на B Перенести диск с A на C Перенести диск с B на C Перенести диск с B на A Перенести диск с C на A Перенести диск с B на C Перенести диск с A на B Перенести диск с A на C Перенести диск с B на C Количество перемещений 2 n -1