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

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

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

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

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

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

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

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

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

9 Треугольник Серпинского

10 Фракталы

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

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

13 Примеры рекурсивного определения в математике. 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,...;

14 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 …

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

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

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

18 Рассмотрим последовательность вызовов этой функции для 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;

19 Возвращаемся назад поднимаясь вверх по цепочке рекурсивных вызовов. Ответ: 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.

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

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

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

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