Рекурсия (RECURCIО возвращение). Цели урока Продолжим изучение подпрограмм. Узнаем, что такое рекурсия, как выполняется рекурсивный алгоритм. - презентация

1 Рекурсия (RECURCIО возвращение)

2 Цели урока Продолжим изучение подпрограмм. Узнаем, что такое рекурсия, как выполняется рекурсивный алгоритм.

3 Что такое подпрограмма? подпрограмма это специальным образом оформленный алгоритм, который может многократно использоваться при решении более общей задачи.

4 Что такое формальные и фактические параметры? Формальные – условные обозначения в описании процедуры – описываются в ее заголовке. Фактические – с которыми требуется выполнить процедуру – перечисляются при вызове процедуры.

5 Что такое функция? Подпрограмма, имеющая единственный результат, может быть оформлена, как функция.

6 К чему относится описание типа в конце заголовка подпрограммы функции? Это описание относится к имени функции, которому необходимо присвоить значение результата.

7 Что такое рекурсивный объект и каковы его свойства Если поставить два зеркала напротив друг друга и между ними поместить предмет, то получится бесконечное множество отображений, причем каждое из них содержит свое собственное отображение. Любое из этих изображений можно рассматривать как рекурсивный объект, который частично состоит или определяется с помощью самого себя.

8 Треугольник Серпинского Берётся сплошной равносторонний треугольник, на первом шаге из центра удаляется внутренность срединного треугольника. На втором шаге удаляется три срединных треугольника из трёх оставшихся треугольников и т. д. После бесконечного повторения этой процедуры, от сплошного треугольника остаётся подмножество треугольник Серпинского.срединного треугольника

9

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

11

12

13 Юмор Большая часть всех шуток о рекурсии касается бесконечной рекурсии, в которой нет условия выхода. «Чтобы понять рекурсию, нужно сначала понять рекурсию» или «Чтобы что-то сделать, надо что-то сделать».

14 Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии: Рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Йона Тихого», в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки».

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

16 Русская народная сказка-песня «У попа была собака…» являет пример рекурсии: У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: "У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: …

17 Свойства рекурсивных объектов Простота построения; Несхожесть конечного результата с начальными данными; Внутреннее самоподобие.

18 Примеры рекурсивного определения в математике. 1) Определение натурального числа. а) 1 - натуральное число; б) число, следующее за натуральным (т.е. больше его на единицу), есть натуральное число. 2) Арифметическая прогрессия: а)а 1 =а 0 ; б) а n =а n-1 +d. При а 0 =1, d=1 имеем натуральный ряд 1,2,3,... 3) Геометрическая прогрессия: а) а 1 =а 0 ; б) а n =а n-1 *q. При а 0 =2, q=2 имеем степенной ряд 2,4,8,16,32,...;

19 4) Факториал a n =n! (Fасtоr сомножитель) n!=1*2*3*4*5*б*...*n. а)а 1 =1; б) а n =n*а n-1. 5) Числа Фибоначчи. Они определяются следующим образом: x[1]=x[2]=1 x[n]=x[n-1]+x[n-2] при n > 2 Каждый элемент ряда Фибоначчи является суммой двух предшествующих элементов, т.е. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …

20 Леонардо Фибоначчи (Пизанский), годы жизни В «Книге абака» 1202 г. изложил формулы решения квадратного уравнения по образцу ал-Хорезми, в этой книге впервые встречается правило для нахождения суммы членов произвольной арифметической прогрессии. Фибоначчи придумал последовательность натуральных чисел : а) если n

21 Определение, которое задает некоторый объект в терминах более простого случая этого же объекта, называется рекурсивным определением.

22 Вывод: мощность рекурсивного определения заключается в том, что оно позволяет с помощью конечного высказывания определить бесконечное множество объектов. Как и цикл, рекурсивное определение содержит повторения, но каждый раз при этом используются новые данные, т е повторение не является явным.

23 Что такое рекурсия. Рекурсия это способ описания функции или процессов через самих себя. Процесс может быть описан некоторым алгоритмом, называемым в данном случае рекурсивным. В таких алгоритмах выделяется два этапа: 1) «погружение» алгоритма в себя, т.е. применениё определения в «обратную сторону», пока не будет найдено начальное определение, не являющееся рекурсивным; 2) последовательное построение от начального определения до определения с введенным в алгоритм значением.

24 4 Примеры рекурсивных алгоритмов. Функция для вычисления факториала: Function F(n: integer): longin; Веgin If n=1 then F:=1 else:=n*F(n-1) End;

25 Рассмотрим последовательность вызовов этой функции для n=5. 1 вызов (n=5) у:=F(5), так как n1, то управление передается на ветку иначе и функция F:=5*F(4). 2 вызов (n=4), так как n 1, то F:=4*F(3). З вызов (n=З), так как n 1, то F:=3*F(2). 4 вызов (n=2), так как n 1, то F:=2*F(1)=2*1=2.. Function F(n: integer): longin; Веgin If n=1 then F:=1 else:=n*F(n-1) End;

26 Возвращаемся назад поднимаясь вверх по цепочке рекурсивных вызовов. Ответ: 5!=120 Это значение присваивается переменной. 1 вызов (n=5), то F:=5*F(4)=5*24= вызов (n=4), то F:=4*F(3)=4*6=24. 3 вызов (n=3), то F:=3*F(2)=З*2=6.

27 Begin {основная программа} Write(n=); Readln(n); Writeln(fib(,n,)=, fib(n):10:0); End. Function fib(x: integer):real; Begin If x

28 Введите и исполните программы вычисления чисел Фибоначчи. Вычислите 8-е число Фибоначчи Ответ. 21

29 Сколько раз вызывается функция Fib при n=8?

30 Вывод. Подпрограммы функции, делают программу, более наглядной, но рекурсивный вызов функции иногда существенно замедляет работу программы.