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

Какво е рекурсивно дърво?

Рекурсивното дърво е графично представяне, което илюстрира потока на изпълнение на рекурсивна функция. Той предоставя визуална разбивка на рекурсивни повиквания, показвайки напредъка на алгоритъма, докато се разклонява и в крайна сметка достига базов случай. Дървовидната структура помага при анализирането на времевата сложност и разбирането на рекурсивния процес.

Дървовидна структура

Всеки възел в рекурсивно дърво представлява конкретно рекурсивно извикване. Първоначалното повикване е изобразено в горната част, а следващите повиквания се разклоняват под него. Дървото расте надолу, образувайки йерархична структура. Факторът на разклоняване на всеки възел зависи от броя на рекурсивните извиквания, направени във функцията. Освен това дълбочината на дървото съответства на броя на рекурсивните извиквания преди достигане на основния случай.

Основен случай

Базовият случай служи като условие за прекратяване на рекурсивна функция. Той определя точката, в която рекурсията спира и функцията започва да връща стойности. В рекурсивно дърво възлите, представляващи основния случай, обикновено се изобразяват като листови възли, тъй като те не водят до допълнителни рекурсивни извиквания.

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

Дъщерните възли в рекурсивно дърво представляват рекурсивните извиквания, направени в рамките на функцията. Всеки дъщерен възел съответства на отделно рекурсивно извикване, което води до създаването на нови подпроблеми. Стойностите или параметрите, предадени на тези рекурсивни извиквания, може да се различават, което води до вариации в характеристиките на подпроблемите.

Поток на изпълнение:

Преминаването през дърво на рекурсия дава представа за потока на изпълнение на рекурсивна функция. Започвайки от първоначалното извикване в основния възел, следваме разклоненията, за да стигнем до следващите извиквания, докато не срещнем основния случай. Когато се достигнат базовите случаи, рекурсивните извиквания започват да се връщат и съответните им възли в дървото се маркират с върнатите стойности. Обхождането продължава, докато не бъде обходено цялото дърво.

Анализ на времевата сложност

Рекурсивните дървета помагат при анализирането на времевата сложност на рекурсивните алгоритми. Чрез изследване на структурата на дървото можем да определим броя на направените рекурсивни повиквания и извършената работа на всяко ниво. Този анализ помага за разбирането на цялостната ефективност на алгоритъма и идентифицирането на потенциални неефективности или възможности за оптимизация.

Въведение

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

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• Рекурсията е илюстрирана от функцията, която беше спомената по-рано. Извикваме функция, за да определим факториела на число. След това, при дадена по-малка стойност на същото число, тази функция се извиква сама. Това продължава, докато стигнем до основния случай, в който няма повече извиквания на функции.
• Рекурсията е техника за справяне със сложни проблеми, когато резултатът зависи от резултатите от по-малки случаи на същия проблем.
• Ако мислим за функции, една функция се нарича рекурсивна, ако продължава да се извиква, докато достигне основния случай.
• Всяка рекурсивна функция има два основни компонента: базов случай и рекурсивна стъпка. Спираме да преминаваме към рекурсивната фаза, щом стигнем до основния случай. За да се предотврати безкрайна рекурсия, базовите случаи трябва да бъдат правилно дефинирани и са от решаващо значение. Определението за безкрайна рекурсия е рекурсия, която никога не достига основния случай. Ако програмата никога не достигне основния случай, препълването на стека ще продължи да се случва.

Типове рекурсия

Най-общо казано, има две различни форми на рекурсия:

• Линейна рекурсия
• Дървовидна рекурсия
• Линейна рекурсия

Линейна рекурсия

• За функция, която се извиква само веднъж всеки път, когато се изпълни, се казва, че е линейно рекурсивна. Хубава илюстрация на линейната рекурсия е функцията факториел. Името „линейна рекурсия“ се отнася до факта, че изпълнението на линейно рекурсивна функция отнема линейно време.
• Разгледайте псевдокода по-долу:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Ако разгледаме функцията doSomething(n), тя приема параметър с име n и прави някои изчисления, преди да извика отново същата процедура, но с по-ниски стойности.
• Когато методът doSomething() се извика със стойността на аргумента n, да кажем, че T(n) представлява общото време, необходимо за завършване на изчислението. За това можем също така да формулираме рекурентна връзка, T(n) = T(n-1) + K. K служи като константа тук. Константата K е включена, защото отнема време на функцията да разпредели или освободи памет за променлива или да извърши математическа операция. Използваме K, за да определим времето, тъй като то е толкова малко и незначително.
• Времевата сложност на тази рекурсивна програма може просто да се изчисли, тъй като в най-лошия сценарий методът doSomething() се извиква n пъти. Формално казано, времевата сложност на функцията е O(N).

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

• Когато направите рекурсивно повикване във вашия рекурсивен случай повече от веднъж, това се нарича дървовидна рекурсия. Ефективна илюстрация на дървовидната рекурсия е последователността на Фибоначи. Дървовидните рекурсивни функции работят в експоненциално време; те не са линейни в своята времева сложност.
• Разгледайте псевдокода по-долу,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• Единствената разлика между този код и предишния е, че този прави още едно извикване на същата функция с по-ниска стойност на n.
• Нека поставим T(n) = T(n-1) + T(n-2) + k като рекурентна връзка за тази функция. K отново служи като константа.
• Когато се извършва повече от едно извикване на една и съща функция с по-малки стойности, този вид рекурсия е известна като дървовидна рекурсия. Интригуващият аспект сега е: колко време отнема тази функция?
• Направете предположение въз основа на рекурсивното дърво по-долу за същата функция.
  
• Може да ви хрумне, че е предизвикателство да оцените времевата сложност, като погледнете директно рекурсивна функция, особено когато е дървовидна рекурсия. Методът на рекурсивното дърво е една от няколкото техники за изчисляване на времевата сложност на такива функции. Нека го разгледаме по-подробно.

Какво представлява методът на рекурсивното дърво?

• Рекурентни отношения като T(N) = T(N/2) + N или двете, които разгледахме по-рано в раздела за видовете рекурсия, се решават с помощта на подхода на дървото на рекурсията. Тези повтарящи се отношения често използват стратегията 'разделяй и владей', за да се справят с проблемите.
• Отнема време за интегриране на отговорите на по-малките подпроблеми, които се създават, когато по-голям проблем се раздели на по-малки подпроблеми.
• Отношението на повторение, например, е T(N) = 2 * T(N/2) + O(N) за сортиране чрез сливане. Времето, необходимо за комбиниране на отговорите на два подпроблема с общ размер T(N/2) е O(N), което е вярно и на ниво реализация.
• Например, тъй като релацията на повторение за двоично търсене е T(N) = T(N/2) + 1, знаем, че всяка итерация на двоично търсене води до пространство за търсене, което е нарязано наполовина. След като резултатът е определен, излизаме от функцията. Отношението на повторение има добавен +1, защото това е операция с постоянно време.
• Рекурентната връзка T(n) = 2T(n/2) + Kn трябва да се вземе предвид. Kn обозначава количеството време, необходимо за комбиниране на отговорите на n/2-мерни подпроблеми.
• Нека изобразим рекурсивното дърво за гореспоменатата рекурентна релация.

Можем да направим няколко заключения от изучаването на рекурсивното дърво по-горе, включително

1. Големината на проблема на всяко ниво е всичко, което има значение за определяне на стойността на възел. Размерът на емисията е n на ниво 0, n/2 на ниво 1, n/2 на ниво 2 и т.н.

2. Като цяло, ние определяме височината на дървото като равна на log (n), където n е размерът на проблема, а височината на това рекурсивно дърво е равна на броя на нивата в дървото. Това е вярно, тъй като, както току-що установихме, стратегията 'разделяй и владей' се използва от рекурентни отношения за решаване на проблеми и достигането от проблем с размер n до проблем с размер 1 просто изисква извършване на log (n) стъпки.

• Помислете за стойността на N = 16, например. Ако ни е позволено да разделяме N на 2 на всяка стъпка, колко стъпки са необходими, за да получим N = 1? Като се има предвид, че делим на две на всяка стъпка, правилният отговор е 4, което е стойността на log(16) с основа 2.

log(16) база 2

log(2^4) основа 2

4 * log(2) основа 2, тъй като log(a) основа a = 1

така че 4 * log(2) основа 2 = 4

3. На всяко ниво вторият член в повторението се счита за корен.

Въпреки че думата „дърво“ се появява в името на тази стратегия, не е нужно да сте експерт по дърветата, за да я разберете.

Как да използваме рекурсивно дърво за решаване на рекурентни релации?

Цената на подпроблема в техниката на рекурсивното дърво е количеството време, необходимо за решаване на подпроблема. Следователно, ако забележите фразата „цена“, свързана с дървото на рекурсията, тя просто се отнася до времето, необходимо за решаване на определен подпроблем.

Нека разберем всички тези стъпки с няколко примера.

Пример

Помислете за рекурентната връзка,

T(n) = 2T(n/2) + K

Решение

Дадената рекурентна връзка показва следните свойства,

Проблем с размер n е разделен на два подпроблема, всеки с размер n/2. Цената за комбиниране на решенията на тези подпроблеми е K.

Всеки проблем с размер n/2 е разделен на два подпроблема, всеки с размер n/4 и така нататък.

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

Нека следваме стъпките, за да разрешим тази връзка на повторение,

Стъпка 1: Начертайте рекурсивното дърво

Стъпка 2: Изчислете височината на дървото

Тъй като знаем, че когато непрекъснато разделяме число на 2, идва момент, когато това число се редуцира до 1. Същото като с размера на проблема N, да предположим, че след K деления на 2, N става равно на 1, което предполага, ( n / 2^k) = 1

Тук n / 2^k е размерът на проблема на последното ниво и винаги е равен на 1.

Сега можем лесно да изчислим стойността на k от горния израз, като вземем log() от двете страни. По-долу е по-ясно извеждане,

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) при основа 2

Така че височината на дървото е log (n) основа 2.

ако иначе баш

Стъпка 3: Изчислете цената на всяко ниво

• Разходи на ниво-0 = K, два подпроблема се обединяват.
• Разходи на ниво-1 = K + K = 2*K, два подпроблема се обединяват два пъти.
• Разходи на ниво-2 = K + K + K + K = 4*K, два подпроблема се обединяват четири пъти. и така нататък....

Стъпка 4: Изчислете броя на възлите на всяко ниво

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

• Ниво-0 има 1 (2^0) възел
• Ниво-1 има 2 (2^1) възела
• Ниво-2 има 4 (2^2) възела
• Ниво-3 има 8 (2^3) възела

Така че нивото log(n) трябва да има 2^(log(n)) възли, т.е. n възли.

Стъпка 5: Обобщете цената на всички нива

• Общите разходи могат да бъдат записани като,
• Обща цена = Цената на всички нива с изключение на последното ниво + Цената на последното ниво
• Обща цена = цена за ниво-0 + цена за ниво-1 + цена за ниво-2 +.... + цена за ниво-log(n) + цена за последно ниво

Цената на последното ниво се изчислява отделно, тъй като това е базовият случай и не се извършва сливане на последното ниво, така че цената за решаване на един проблем на това ниво е някаква постоянна стойност. Нека го приемем като O (1).

Нека поставим стойностите във формулите,

• T(n) = K + 2*K + 4*K + .... + log(n)` пъти + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) пъти)' + 'O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) пъти + O(n)

Ако погледнете внимателно горния израз, той образува геометрична прогресия (a, ar, ar^2, ar^3 ...... безкрайно време). Сумата от GP се дава от S(N) = a / (r - 1). Ето първия член и r е общото съотношение.