Рекурсия вокруг нас сообщение

Обновлено: 02.07.2024

После того как вы поделитесь материалом внизу появится ссылка для скачивания.

Подписи к слайдам:

Автор: Фоминова Елена Владимировна,

учитель физики и информатики

МБОУ СОШ № 23 МО Усть-Лабинский район хутора Братского Краснодарского края

Теория
Рекурсия вокруг нас
Рекурсия в математике
Программирование
Задачи на закрепление
Список использованной литературы

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

Что нужно знать:

Рекурсия может быть прямой и косвенной.

Рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа.

Чтобы определить рекурсию, нужно задать:

-условие остановки рекурсии

Любую рекурсивную процедуру можно запрограммировать с помощью цикла

Рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным.

Рекурсия может быть прямой и косвенной.

В случае прямой рекурсии вызов функцией самой себя делается непосредственно в этой же функции

procedure F(n: integer);

if n > 1 then begin

Косвенная рекурсия создаётся за счёт вызова

данной функции из какой-либо другой функции,

которая сама вызывалась из данной функции.

function F(n: integer): integer;

if n > 2 then F := F(n - 1) + G(n - 2)

function G(n: integer): integer;

if n > 2 then G := G(n - 1) + F(n - 2)

Уроборос – змей, кусающий свой собственный хвост. Это древний символ бесконечности Вселенной и времени, круговорота жизни, отождествляемых с рекурсией. Уроборос – змей, кусающий свой собственный хвост. Это древний символ бесконечности Вселенной и времени, круговорота жизни, отождествляемых с рекурсией.

Рекурсия вокруг нас…

Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала: в них образуются два коридора из затухающих отражений зеркал.

Классическим примером конечной рекурсии является русская матрешка.

"Мастер и Маргарита" - один из наиболее ярких рекурсивных романов.

Тема Иешуа и Пилата рекурсивно вызывается из темы Мастера и Маргариты. Кроме того, здесь так же используется прием "книга в книге". Мастер пишет роман об Иешуа и Пилате, текст которого сливается с текстом книги "Мастер и Маргарита".

Рекурсия вокруг нас… Первым романом, удивившим читателей приемом рекурсии, был "Дон Кихот". Сервантес все время пытался смешивать два мира: мир читателя и мир книги. У Сервантеса главный процесс не просто книга, но книга плюс читатель. В шестой главе цирюльник, осматривая библиотеку Дон Кихота, находит книгу Сервантеса и высказывает суждения о писателе. Вымысел Сервантеса рассуждает о нем. В начале девятой главы сообщается, что роман переведен с арабского и что Сервантес купил его на рынке. Наконец, во второй части романа персонажи уже прочли первую часть.

Элементы использования рекурсии находим еще раньше у Шекспира. Гамлет ставит спектакль, где в упрощенном варианте описываются события трагедии.

Рекурсия вокруг нас…

У попа была собака, он её любил Она съела кусок мяса, он её убил В землю закопал, Надпись написал: «У попа была собака, он её любил Она съела кусок мяса, он её убил В землю закопал, Надпись написал:

С. Маршака Вот дом, Который построил Джек. А это пшеница, Которая в темном чулане хранится В доме, Который построил Джек А это веселая птица-синица, Которая часто ворует пшеницу, Которая в темном чулане хранится.

Рекурсия вокруг нас…

А. Блока Ночь, улица, фонарь, аптека. Бессмысленный и тусклый свет. Живи еще хоть четверть века – Все будет так. Исхода нет. Умрешь – начнешь опять сначала, И повторится все, как встарь: Ночь, ледяная рябь канала, Аптека, улица, фонарь.

Рекурсия вокруг нас…

Эйфелева Башня в Париже

Исторический музей в Москве

Рекурсия вокруг нас…

Дерево состоит из веток. Ветка в свою очередь состоит из более маленьких веточек. Каждая ветка повторяет дерево.

Реки образуются из впадающих в них рек.

Чешуя шишек и семена некоторых цветов (например, подсолнечника) расположены пересекающимися

спиралевидными веерами, определяемыми соотношением чисел Фибоначчи.

Эффект Дросте - термин для изображения специфического вида рекурсивного изображения. Изображение включает уменьшенный собственный вариант самого себя. Этот более малый вариант после этого показывает даже более малый вариант себя, и так далее. Практически это продолжается пока разрешение изображения позволяет уменьшает размер. Термин был введен в честь Дросте, голландского какао.

Рекурсия вокруг нас…

Герб Российской Федерации

является рекурсивно-определённым графическим объектом: в правой лапе изображённого на нём двуглавого орла зажат скипетр, который венчается уменьшенной копией герба. Так как на этом гербе в правой лапе орла также находится скипетр, получается бесконечная рекурсия.

Рекурсия в математике 1) Арифметическая прогрессия: а)а1=а0; б) аn=аn-1+d. 2) Геометрическая прогрессия: а) а1=а0; б) аn=а n-1*q. Рекурсия в математике 3) Факториал an=n! n!=1*2*3*4*5*б*. *n. а)а1=1; б) аn=n*аn-1. 4) Числа Фибоначчи. x1=x2=1 xn=xn-1+xn-2 при n > 2 Каждый элемент ряда Фибоначчи является суммой двух предшествующих элементов, т.е. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,… Программирование

Рекурсия — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе.

В программировании рекурсия — вызов функции из неё же самой, непосредственно или через другие функции, например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Программирование В языке программирования Pascal рекурсивностью могут обладать как функции, так и процедуры. Примеры рекурсивной процедуры. Общая форма записи: Procedure Rec (a:integer); Begin If a>0 Then Rec(a-1); Writeln(a); End;

Выполнение рекурсивного алгоритма можно представить следующим образом:

каждый рекурсивный вызов процедуры F порождает в памяти компьютера новую копию этой процедуры и запускает ее на выполнение со своими значениями входных параметров.

После того как процедура F завершила работу, выполнение программы продолжается со следующего оператора после вызова F.

Программирование Пример рекурсивной процедуры: Program n1; uses crt; procedure Rec(i: integer); begin if i>1 then Rec(i-1); writeln(i); end; begin clrscr; Rec(5); End.

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Описание презентации по отдельным слайдам:

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

Порождение все новых копий рекурсивной подпрограммы до выхода на граничное условие называется рекурсивным спуском. Максимальное количество копий рекурсивной подпрограммы, которое одновременно может находиться в памяти компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным подъёмом.

Рекурсия обычно состоит из двух частей: базовой и рекурсивной. Базовая часть – нерекурсивное определение, которое задаёт определение для некоторой фиксированной группы объектов. Рекурсивная часть – содержит определение для произвольной группы объектов и построена на основе базы.

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

Одним из примеров рекурсивной функции могут служить числа Фибоначчи —элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … в которой каждое последующее число равно сумме двух предыдущих чисел. Название по имени средневекового математика Леонардо Пизанского (или Фибоначчи). База состоит из двух определений: Первое число последовательности = 1 второе число последовательности = 1 Рекурсия: An= An-1 + An-2 Эти числа ввёл в 1202 г. Леонардо Фибоначчи

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

В математике достаточно широко применяют рекурсию. Факториал целого неотрицательного числа n обозначается n! И определяется как n!=n*(n-1)! при n>0 и n!=1 при n=0 Практически все геометрические фракталы задаются в форме бесконечной рекурсии. Треугольник Серпинского

Классическим примером бесконечной рекурсии являются два поставленные друг на против друга зеркала: в них образуются два коридора из затухающих отражений зеркал. Другим примером бесконечной рекурсии является эффект самовозбуждения (положительной обратной связи) у электронных схем усиления, когда сигнал с выхода попадает на вход, усиливается, снова попадает на вход схемы и снова усиливается. Усилители, для которых такой режим работы является штатным, называются автогенераторы.

Эффект Droste Термин для изображения специфического вида рекурсивного изображения. Изображение включает уменьшенный собственный вариант самого себя. Этот более малый вариант после этого показывает даже более малый вариант себя, и так далее. Термин был введен в честь Droste, голландского какао. Рекурсия в искусстве

Рекурсия – вызов функции из неё же самой (обычно с другими значениями входных параметров), непосредственно или через другие функции. Мощь рекурсивного определения объекта в том, что такое конечное определение способно описывать бесконечное вычисление, причём без явных повторений частей программы.

Простая линейная рекурсия Параллельная рекурсия Взаимная рекурсия Рекурсии более высокого порядка

Рекурсия и итерация взаимозаменяемы. Итерация в основном используется для тех видов обработки, которые можно определить выражением "выполнить для всех", а рекурсия задается выражением "выполнить тоже, что и в последний раз". В случае итерации, текущее действие выполняется с помощью предыдущего ответа или предыдущих стадий вычисления. Теорема. Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде, и наоборот.

Оба алгоритма имеют линейную сложность, но для рекурсивной процедуры требуются дополнительные расходы памяти и времени, т.к. происходит многократное обращение из подпрограммы к самой себе. Должно создаваться и сохраняться много копий регистров, переменных и точек возврата. Для хранения этой информации используется стековая память, поэтому предпочтительнее итерационная форма. fact (int n) < if (n == 0) return 1; else return n*fact(n-1); >fact (2); fact (2) < if (n == 0) return 1; else return 2*fact(2-1); >fact (1) < if (n == 0) return 1; else return 1*fact(1-1); >fact (0)

function Fakt(N:integer):longint; begin if N=0 then Fakt:=1 else Fakt:=N*Fakt(N-1); end; Function Fact(n:word):word; Var i,k : word; Begin k:=1; For i:=1 to n do k:=k*i; Fact:=k; End; С использованием рекурсии Без использования рекурсии

Function F(n:byte):longint; begin if n m then h:=Evklid(n,m) Else If n=0 then h:=m Else h:=Evklid(n, m mod n); Evklid:=h; End < Evklid >; Эвклид - древнегреческий математик, автор первых дошедших до нас теоретических трактатов по математике.

Пример. Возведение в степень. Function Power(x:real; n:word):real; Begin If n=0 then Power:=1 Else Power:=x*Power(x,n-1); End < Power >;

Пример. Рекурсивная процедура convert переводит десятичное число z в восьмеричную систему путем деления его на 8 и выдачи остатка в обратной последовательности. Program dezimal_oktal_konvertierung; var z:integer; procedure convert(z:integer); begin if z > 1 then convert(z div 8); (* Это рекурсивный вызов *) write(z mod 8:1); end; begin writeln(‘Введите положительное число:’); readln(z); writeln(‘Десятичное число:’,z:6); write(‘Восьмеричное число: ’); convert(z); end.

Описать рекурсивную функцию C(m,n) для вычисления биномиального коэффициента по формуле: Составить программу с использованием рекурсивной функции, в которой вычислить сумму 12 членов рекуррентной последовательности

Презентация на тему: " Июнь 2007 1 Рекурсия Итерация свойственна человеку, рекурсия - божественна. Л. Питер Дойч." — Транскрипт:

1 Июнь Рекурсия Итерация свойственна человеку, рекурсия - божественна. Л. Питер Дойч

2 Июнь Основные вопросы Основные понятия. Основные понятия. Виды рекурсии. Виды рекурсии. Область применения рекурсивных функций. Область применения рекурсивных функций. Достоинства и недостатки рекурсии. Достоинства и недостатки рекурсии. Замена рекурсии итерацией. Замена рекурсии итерацией. Замена итерации рекурсией. Замена итерации рекурсией. Особенности работы с памятью Особенности работы с памятью

4 Июнь Прямая и косвенная рекурсии Прямая рекурсия – вызов подпрограммы непосредственно в ее теле Прямая рекурсия – вызов подпрограммы непосредственно в ее теле Косвенная рекурсия – вызов подпрограммы через другие подпрограммы, например, когда процедура А вызывает процедуру B, процедура B – процедуру C, процедура C – процедуру А. Косвенная рекурсия – вызов подпрограммы через другие подпрограммы, например, когда процедура А вызывает процедуру B, процедура B – процедуру C, процедура C – процедуру А.

5 Июнь Пример прямой рекурсии – вычисление факториала int Fact(int n)< if(n 1)?(n* Fact(n-1):1; >… int res = Fact(4); 1. Вызов Fact(4) 1. Вызов Fact(3) 1. Вызов Fact(2) 1. Вызов Fact(1) 1. Возврат 1 2. Возврат 1*2 2. Возврат 2*3 2. Возврат 6*4 2. res = 24;

6 Июнь Состав рекурсивной функции Проверка, достигнуто ли граничное значение. Проверка, достигнуто ли граничное значение. Если достигнуто – вычисляется возвращаемое значение без рекурсивного вызова. Если достигнуто – вычисляется возвращаемое значение без рекурсивного вызова. Если граничное значение не достигнуто – используется рекурсивный вызов с более простым параметром (параметром, который ближе к граничному значению). Если граничное значение не достигнуто – используется рекурсивный вызов с более простым параметром (параметром, который ближе к граничному значению).

7 Июнь Область применения рекурсии 1. Компактная реализация рекурсивных алгоритмов 2. Работа со структурами данных, которые описаны рекурсивно, например, двоичные деревья.

8 Июнь Двоичное дерево

9 Июнь Достоинства и недостатки рекурсии Компактная запись, лаконичность при реализации рекурсивных алгоритмов Компактная запись, лаконичность при реализации рекурсивных алгоритмов Накладные расходы на дополнительные вызовы функций Накладные расходы на дополнительные вызовы функций Возможность переполнения стека Возможность переполнения стека Сложность алгоритма для понимания Сложность алгоритма для понимания

10 Июнь Вычисление факториала Возвращаемое значение 1 Параметр 1 Адрес возврата Возвращаемое значение 2 Параметр 2 Адрес возврата Возвращаемое значение 6 Параметр 3 Адрес возврата Возвращаемое значение 24 Параметр 4 Адрес возврата Вызов Fact(4) Вызов Fact(3) Вызов Fact(2) Вызов Fact(1) Если в функции используются локальные переменные, то под них также будет резервироваться место в стеке

11 Июнь Использование глобальных переменных В рекурсивных функциях использование глобальных переменных ограничено В рекурсивных функциях использование глобальных переменных ограничено Модификация глобальной переменной отразится на всей цепочке вызовов функции. Модификация глобальной переменной отразится на всей цепочке вызовов функции. Невозможно определить на каком шаге рекурсии была модифицирована глобальная переменная. Невозможно определить на каком шаге рекурсии была модифицирована глобальная переменная.

12 Июнь Замена рекурсии итерацией Любую рекурсивную функцию можно реализовать без применения рекурсии, для этого программист должен обеспечить хранение всех необходимых данных Любую рекурсивную функцию можно реализовать без применения рекурсии, для этого программист должен обеспечить хранение всех необходимых данных int Fact(int n)< int res = 1; for(int i = 1; i

13 Июнь Замена итерации рекурсией Любую итерацию можно заменить с помощью рекурсии Любую итерацию можно заменить с помощью рекурсии void fill(int *m, int size)< for(int i = 0; i

14 Июнь Вопросы к экзамену Рекурсия. Основные понятия. Виды рекурсии. Область применения рекурсивных функций. Достоинства и недостатки рекурсии. Замена рекурсии итерацией. Замена итерации рекурсией. Рекурсия. Основные понятия. Виды рекурсии. Область применения рекурсивных функций. Достоинства и недостатки рекурсии. Замена рекурсии итерацией. Замена итерации рекурсией.

В программировании рекурсия, или же рекурсивная функция — это такая функция, которая вызывает саму себя.

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

Не приведёт ли рекурсивная функция к бесконечному циклу?

Да, такой исход вполне возможен. Однако, как и у функции for или while , рекурсию можно прервать условием break , чтобы функция перестала вызывать саму себя.

Вот пример кода того, как можно реализовать функцию обратного отсчёта с использованием рекурсии:

Как прервать рекурсию:

Допустим, у нас имеется функция CountDown , которая принимает аргумент (n) . Чтобы реализовать обратный отсчёт, нам следует повторить последовательность действий, понижающих значение параметра. Создадим условие вида:

Если (n) больше 1 , то вызвать функцию CountDown и вернуться в начало цикла, затем вычесть единицу и снова проверить, выполняется ли условие (n) > 1 .

По умолчанию нам нужно создать базовое условие функции, возвращающее значение true , чтобы предотвратить попадание в бесконечный цикл. Базовым условием функции здесь будет условие о том, что любое значение больше 1 не вызовет прерывание цикла.

Проще говоря, рекурсия делает то же, что и код ниже:

Плюсы и минусы рекурсивных функций

Чтобы правильно описать плюсы и минусы, давайте взглянем на производительность рекурсии.

Плюсы:

Рекурсивный код снижает время выполнения функции.

Под этим подразумевается, что рекурсии, в сравнении с циклами, тратят меньше времени до завершения функции. Чем меньше строк кода у нас будет, тем быстрее функция будет обрабатывать вызовы внутри себя. Особенно хорошо это проявляется при буферизации данных, что позволяет оптимизировать и ускорить код.

В программировании мемоизация — это метод сохранения результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения программ. — Википедия

И всё же стоит отметить, что рекурсия не всегда выигрывает по скорости по сравнению с циклами.

Многие согласятся, что эта причина очень важна. Рекурсия проста в отладке из-за того, что она не содержит сложных и длинных конструкций.

Минусы:

Рекурсивные функции занимают много места.

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

Рекурсивные функции замедляют программу.

Несмотря на то, что уже было сказано про мемоизацию, наш код можно ускорить, если применить циклы for или while . Помимо того, что функция может быть попросту плохо написана, мы также рискуем переполнить стек, что в конечном итоге приведёт к снижению скорости и программным ошибкам.

Стоит ли использовать рекурсии вместо обычных циклов?

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

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

Циклы так же эффективны в плане скорости и оптимизации, они занимают меньше памяти в стеке и их легче понять, потому что в теле цикла содержится больше информации о том, что происходит внутри.

Читайте также: