Рекурсия Учитель информатики Дружковской общеобразоватьльной школы І-ІІІ ступеней 17 Фёдорова Татьяна Викторовна. - презентация

1 Рекуроссия Учитель информатики Дружковской общеобразовательной школы І-ІІІ ступеней 17 Фёдорова Татьяна Викторовна

2 Нужна ли рекуроссия человеку в различных областях его деятельности? Рекуроссия нужна, потому что правилам рекурсии подчиняются: литература и поэзия; графика и музыка; окружающая природа и процесс мышления человека.

3 Рекурсии в математике Это правильный шестиугольник, на каждой стороне которого нарисован правильный шестиугольник, на каждой стороне которого нарисован правильный шестиугольник, и так далее.

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

5 Рекурсии в природе Чтобы найти другие примеры рекурсии в природе необходимо оглянуться вокруг и поискать... Дендриты – рекурсивные образования в природе Снежинки - это ледяные дендриты Встречаются дендриты меди, золота, серебра

6 Рекурсии в графике Рекурсию можно обнаружить в произведениях многих художников нашего времени. Например, она занимает значительное место в произведениях сюрреалиста С.Дали. Художник экспериментирует как с «рамочной» рекурсией вложенности, так и рекурсией повторов изображений.

7 Давно известен такой приём, как разбиение задачи на простые шаги, каждый из которых тоже можно разложить на еще более мелкие и так далее, пока не доберёмся до самых элементарных «шажочков». Вот это и есть рекуроссия. Таким образом, Реку́россия частичное определение объекта через себя. ОШ 17, Фёдорова Т. В.

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

9 Оболочка (0) - матрешка Оболочка (1) - матрешка Оболочка (2) - матрешка Оболочка (3) - матрешка … Матрешка Ξ Оболочка[Матрешка] ОШ 17, Фёдорова Т. В.

10 Виды рекурсии Например, функция а вызывает функцию б, а функция б функцию а. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Рекуроссия простая рекуроссия-вызов функции (процедуры) из неё же самой, непосредственно сложная или косвенная рекуроссия- вызов функции через другие функции

11 Это как если бы Вы поставили друг перед другом два зеркала. Что там увидите? Бесконечное их отражение, своего рода коридор из зеркал. Это и будет одна из форм бесконечной рекурсии. Пример. Представим, что нужно пройти 1000 шагов. Для решения делаем один шаг, остаётся 999: задача упростилась. Сделав такое упрощение 999 раз, дойдём до самой элементарной задачи шагнуть один раз. ОШ 17, Фёдорова Т. В.

12 У рекурсии есть: база аргументы, для которых значения функции определены (элементарные задачи), шаг рекурсии способ сведения задачи к более простым. ОШ 17, Фёдорова Т. В.

13 Procedure Rec( ); Begin … If Then Rec(n-1); … End; ОШ 17, Фёдорова Т. В.

14 P рекурсивная подпрограмма. ОШ 17, Фёдорова Т. В.

15 Задачи с рекурсивной формулировкой. Задачи, из постановки которых можно извлечь рекурсию. Задачи, которые можно решить, как частный случай обобщений. Задачи, в которых можно использовать характеристику или свойство функции. ОШ 17, Фёдорова Т. В.

16 1, при N=1 N*(N-1)!, при N>1 N!= ОШ 17, Фёдорова Т. В.

17 1 N=5 2 N=4 3 N=3 4 N=2 5 N=1 Fk:=1 Fk:=1*2=2 Fk:=2*3=6Fk:=6*4=24Fk:=24*5=120 Найдём 5! ОШ 17, Фёдорова Т. В.

18 Многие задачи не являются рекурсивными по определению, но можно попытаться свести некоторые из них к рекурсивным. Пример – нахождение НОД двух целых чисел. Алгоритм Евклида Если a=0 или b=0, то НОД(a, b) = a+b; если ab, то НОД(a, b)= НОД(a-b, b); если a

19 abанализ a>b ab a