основни дефиниции

Тя се нарича рекурсивна дефиниция на обекта през един и същ обект.

В този пример, рекурсивен част на определянето е "<Список> '' <Число> ".

Забележка 1. рекурсивно определение, е крайно, определя безкраен брой обекти.

Имайте предвид също така, че <Список> Тя може да бъде определен по различен начин:

Определението (1) наляво рекурсивно повикване. и (2) - Право рекурсия.

Забележка 2. В рекурсивно определение се изисква (.) Трябва да присъства не-рекурсивни част.

Рекурсивно определение може да бъде индиректно.

един от клоновете на рекурсивни дефиниции, посочени обект, за определянето на които, от своя страна, едно от разклоненията се определя от обекта източник.

В този пример има преки и непреки рекурсивно определение.

В програмирането на рекурсия означава:

• обадете се на себе си подпрограмата (пряка рекурсия)
• обадете друга подпрограма на подпрограмата, която причинява източника (непряка рекурсия)

Прости примери за използване на рекурсия

Когато се обадите на тази процедура ще рекурсивни линия. защото рекурсивно повикване се прави безусловно.

Заключение. За да не се е случило рекурсивни линия, рекурсивни повикването трябва да се извършва не абсолютно, но в някои състояние, което се променя всеки път, а някои рекурсивно повикване стане неверен (т.нар продължаване състояние на рекурсия).

Ние коригира нашите процедури в съответствие със сключения:

Когато наречен Р (0) да се показва:

Графично, рекурсивни повиквания могат да бъдат представени, както следва:

Технологичните последователни рекурсивни разговори на самия подпрограмата се нарича рекурсивно спускане.
Процесът на връщане на рекурсивни повиквания се нарича рекурсивна замяна.

В този пример, броят показва на рекурсивно спускане (т.е., в напред ред).
Въпреки това, действията, извършвани в обратен ред, от които се нуждаят, за да се обадя на рекурсивни декларация.

Пример 2. оттегли

Максималната дълбочина на рекурсивни повиквания се нарича дълбочина рекурсия.
Текущ дълбочина се нарича сегашното ниво на рекурсия.

Забележка. Колкото по-голяма дълбочина на рекурсия, толкова повече памет режийните.

Графични рекурсивни повиквания

Една картина вече имахме. Нека да го запомни:

Помислете за по-подробно за повикване P (0) Процедури

• Софтуер комин - е непрекъсната област от паметта, отпуснат на програмата, по-специално, за получаване на наричат ​​подпрограми.
• За всяко извикване на стека на подпрограма се поставя неговото активиране запис (ЗА), и когато се върнете - се отстранява от стека.

по този начин в стека всъщност съдържа цялата стойност на променливата аз.

Забележка 1. Тъй като всеки рекурсивни стека повикване се поставя зад себе си, с голямата дълбочина на рекурсия софтуер стека може да изтече. и програмата ще се провалят.
Това ще се случи по-бързо, толкова по-общия размер на формалните параметри и локални променливи.

Затова следния код - много лошо.

Забележка 2. Отгоре за поставяне върху купчина разходи при удара върху пакета, както и присвояване на стойностите на формалните параметри на комина са достатъчно големи.
Ето защо, ако има едно просто решение за не-рекурсивни (повтарящ се), е необходимо да го използвате.

Забележка 3. Всяка рекурсия може да бъде заменен от повторение.

Примери на рекурсия

Пример 1: Намерете н! = N (п - 1) (п - 2). 2 * 1
Очевидно е, че се определят н! може, както следва:

Тогава решението е, както следва:

Все пак, имайте предвид, че върнатата стойност не е определена за п <0.
Най-малкото, можете да замените състоянието п = 0, за да п <= 0. но, в таком случае, мы получим неверный результат, т.к. факториал вообще не определен для отрицательных чисел.
Очевидно е, че е необходимо да се провери коректността на одобрението чрез входен параметър (твърдят (п> = 0)). Но използването му във всяка рекурсивно повикване скъпо. Следователно, можете да "обвива" рекурсивни рутината, така:

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

Пример 2. Find. Ние даваме рекурсивно определение:

дълбочина рекурсия е:

• - в най-добрия случай
• - в най-лошия

Пример 3. Определяне на минималната елемент в масива. може да определи този елемент като минималната (един елемент от набор от минимум без този елемент). т.е. рекурсивно определение от следните неща:

В съответствие с това ние имаме решение:

дълбочина рекурсия е п - 1.

Ясно е, че това не е много добър резултат.
Може значително да намали дълбочината, ако погледнем в продължение на минимум за равни части между масива. Т.е. което трябва да се разделят на масива на половина, намери във всяка половина на минималните елементи и да ги сравните. Търсене половината направила това, и разделянето се извършва, когато няма да има никой subarray елемент.
Това може да е малко повече, за да се оптимизира алгоритъма - ако subarray два елемента, което е достатъчно, за да се върнат минимума от тях.
Сега, знаейки, броят на елементите не е достатъчно: трябва да знаете, за да търсите сред някои елементи на масива. Ето защо ние предаваме като параметри наляво (л) и десен (R) субредове граница.
Ние даваме нов рекурсивно определение:

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

Пример 4. Заключение просто свързан линеен списък на екрана.
Спомнете си как списъкът изглежда така:

решение:

Дълбочина на рекурсия е даден списък на дължина - 1

Рекурсия се нарича терминал. ако рекурсивни обаждането е последният в подпрограма.

край рекурсията Най-лесно се превръща в итеративен алгоритъм:

Доказателство zavershimosti рекурсия

Рекурсивно процедура за добавяне на параметъра п.

Ако по време на всеки параметър рекурсивно повикване н намалява получават обаждания

Ако рекурсията е завършена, когато п <= 0. то это служит доказательством завершимости рекурсии.

Наистина, при всяко следващо ниво на рекурсия н става по-малък.
От п <= 0 рекурсивных вызовов нет, то число рекурсивных вызовов конечно.

Твърди се, че рекурсия zavershima, не винаги е възможно.
Пример.

Форма на рекурсивни съчетания

1. Действието се извършва на рекурсивно спускане

2. Действието се извършва на рекурсивни връщането

3. Действието се извършва на рекурсивно спускане и рекурсивни връщане

4. Cascade рекурсия

Това се нарича рекурсия каскада. защото всяка подпрограма разговор може да произведе няколко рекурсивни повиквания (каскада).

5. Дистанционно рекурсия.

Пример за рекурсия е функцията на дистанционното Ackerman.

Примери за добри и лоши на рекурсия

Пример лошо рекурсия - Фибоначи

Числата на Фибоначи се определят от отношението на повторение:

Ние ги изчислява чрез цикъла. Може би рекурсивно (! Лошо) Решение:

Това е, което се случва, когато ти се обадя ПИБ (7).

дърво на рекурсивни повиквания

Както можете да видите, същите номера са изчислени от броя пъти:

Можете да подобрите алгоритъм, като се използва набор от първоначално запълва с нули.
Когато за първи път изчисляване ПИБ (н) ще попълни съответния елемент, и при всички следващи - просто достъп до нейната стойност. Тази техника се нарича memoization. т.е. запомняне на междинните резултати, за да се избегне тяхното преизчисляване.

Очевидно е, че този метод е изключително неефективно в сравнение с един повтарящ се алгоритъм, както в паметта и на работното време. По-специално, изчисляването на дълбочината рекурсия на броя на п-Фибоначи е п-1.

Рекурсивно метод за изчисляване на Фибоначи конструира чрез итеративен алгоритъм

Спомнете си повтарящ алгоритъм за търсене е п-ред Числата на Фибоначи:

Ние се изгради от него рекурсивен алгоритъм, предава всяка рекурсивна подпрограма променливите а, б, в, смяна на всеки цикъл на итерация. В действителност, във всяка рекурсивно повикване, ние ще направим това заместване:

Рекурсивно алгоритъм изпълнява от тази смяна ще бъде:

Рекурсия в този пример - край. Както вече бе отбелязано, че е лесно да се сменят от повторение, само получени предходната решение итерация. Добри оптимизиране компилатори правят това автоматично.

Пример за добро използване на рекурсия - кулите на Ханой

Задачата е, както следва:
Предвид три прът. На земята са п дискове с различни радиуси при условие, че няма диск не по-голям от радиуса на диска от по-малък радиус.
Задължителни колела се движат от първия до третия прът, с помощта на втория, при условие че:

• в един ход, можете да носите само един диск
• по-малък диск трябва да се намира на по-голяма

Идеята на алгоритъма е както следва:

по този начин Ние имаме една проста рекурсивно решение:

Quicksort

Quicksort алгоритъм (алгоритъм разнообразие "разделяй и vlavstvuy") се състои от два етапа:
1. Избор на елемент на разделяне масив масив и х на две части, така че в първата превърне всички елементи <= x, а в о второй —>= х
2. Рекурсивно прилагане на нашия алгоритъм за получените части

Очевидно е, че алгоритъмът ще работи по-бързо от по-равни части, ние ще разделим масива (в идеалния случай - на половина всеки път).
Ето защо, ние трябва да се стремим, за да изберете елемент х такова, че около половината от масива е <= его, и, соответственно, вторая половина —>=. От друга страна, изборът на х трябва да отнеме много време и най-малко не зависи от п - размер на масива).

Ние ще използваме най-простият начин да изберете Х - като го взема първия елемент.

Следваща анимация показва пример за прилагане на алгоритъм за Quicksort масив

Обърнете внимание на детайлите Фаза 1:
- За разделянето на масива на споменатата глава част 2 на индекса и и к.
- В началото аз ще сочи към първия елемент и да се премести на дясно, и Й - последният и да се премести наляво.

Етап 1.
Ще тласък, докато А [Ь] няма да бъде> = х.
Следваща ще се придвижи обратно към й, докато A [д] не ще <= x .
Стигна до елементи А [Ь] и А [й]. които "не са на местата си" (не забравяйте, че ние искаме да се разпръснат всички по-малка или равна на х към левите елементи, както и по-голям или равен - в дясно)
Етап 2.
Разменени тях и аз ще се придвижи напред по един елемент, а й - обратно, като един от елементите.

Ние ги повторите толкова дълго, колкото аз няма да бъде> = к.
Резултатът е масив A. се разделя на 2 части:

програмен код

Един асимтотична оценка на сложността на

Да предположим, че масива всеки път, когато е разделена на 2 равни части. Това е най-добрият вариант.
Дълбочината на рекурсия в този случай = log2 п.

по този начин делението условие приблизително наполовина. асимптотичната сложност на общата алгоритъм = Θ (п влизане п).

Теоретично, това е доказано, че средно, ако не се дели точно на половина, асимптотичния сложността запазва формула Θ (п влезте н).
Въпрос: Каква е сложността в най-лошия случай? Лошия - когато X е избран от минималното (или максимум) елемент. Това се случва (в нашия случай, тъй като сме избрали първия елемент), ако масива вече е сортиран.
В този случай, в резултат на разлагане на парчета голяма част ще бъде намален с 1 и дълбочина процедурата Сортиране на рекурсия ще бъде равен.
Ето защо, в най-лошия случай = асимтотична сложността.

Одобрение. За случайни данни, няма алгоритъм с асимтотична сложност по-добре от Θ (п влезте н) в средната стойност.

Генериране на всички пермутации

Основната идея за генериране на всички пермутации на алгоритъма е следната. В масив с дължина N, съдържащ пермутация, ние ще се промени последният елемент от всеки, а след това рекурсивно ще направи същото за дължината на масива н-1, а след това се върнете на пренаредени елемент на старото си място. Ако дължината на масива се достига п = 1, а след това на суапа не се нуждае от нищо, а трябва да раздаде цялото съдържание на гама-Първообразът на екрана. Такъв алгоритъм позволява да се генерират всички пермутации, което произтича от вербална рекурсивно определение: последно посещение всеки елемент се съдържа в този масив, след което останалата част от масива същия алгоритъм се прилага рекурсивно.

Лесно е да се види, че дълбочината на рекурсия е N-1, както и броя на процедура призовава Перм п.

Генериране на всички подгрупи

Генериране на всички подгрупи е Робин алгоритъм. Алгоритмите за сортиране се движат всички възможности за подходящи възможности за извършване на определени действия. В този случай, просто показва всички подгрупи.

Връщане назад (връщане назад)

Общо схема бюст с връщане