Рекурзија је фундаментални концепт у рачунарству и математици који омогућава функцијама да се позивају, омогућавајући решавање сложених проблема кроз итеративне кораке. Једна визуелна репрезентација која се обично користи за разумевање и анализу извршења рекурзивних функција је стабло рекурзије. У овом чланку ћемо истражити теорију иза стабала рекурзије, њихову структуру и њихов значај у разумевању рекурзивних алгоритама.
Шта је стабло рекурзије?
Стабло рекурзије је графички приказ који илуструје ток извршења рекурзивне функције. Пружа визуелни преглед рекурзивних позива, приказујући напредовање алгоритма како се грана и на крају достиже основни случај. Структура стабла помаже у анализи временске сложености и разумевању укљученог рекурзивног процеса.
Трее Струцтуре
Сваки чвор у стаблу рекурзије представља одређени рекурзивни позив. Почетни позив је приказан на врху, а наредни позиви се гранају испод њега. Дрво расте надоле, формирајући хијерархијску структуру. Фактор гранања сваког чвора зависи од броја рекурзивних позива у оквиру функције. Додатно, дубина стабла одговара броју рекурзивних позива пре достизања основног случаја.
Основни случај
Основни случај служи као услов завршетка за рекурзивну функцију. Дефинише тачку у којој се рекурзија зауставља и функција почиње да враћа вредности. У стаблу рекурзије, чворови који представљају основни случај се обично приказују као лисни чворови, јер не резултирају даљим рекурзивним позивима.
Рекурзивни позиви
Подређени чворови у стаблу рекурзије представљају рекурзивне позиве направљене унутар функције. Сваки подређени чвор одговара посебном рекурзивном позиву, што резултира стварањем нових подпроблема. Вредности или параметри који се прослеђују овим рекурзивним позивима могу се разликовати, што доводи до варијација у карактеристикама подпроблема.
Ток извршења:
Прелазак кроз стабло рекурзије пружа увид у ток извршења рекурзивне функције. Почевши од почетног позива у основном чвору, пратимо гране да бисмо дошли до наредних позива док не наиђемо на основни случај. Како се достигну основни случајеви, рекурзивни позиви почињу да се враћају, а њихови одговарајући чворови у стаблу су означени враћеним вредностима. Обилазак се наставља све док се не пређе цело дрво.
Анализа временске сложености
Стабла рекурзије помажу у анализи временске сложености рекурзивних алгоритама. Испитивањем структуре стабла можемо одредити број извршених рекурзивних позива и обављен посао на сваком нивоу. Ова анализа помаже у разумевању укупне ефикасности алгоритма и идентификацији било које потенцијалне неефикасности или могућности за оптимизацију.
Увод
- Замислите програм који одређује факторијел броја. Ова функција узима број Н као улаз и враћа факторијел од Н као резултат. Псеудо-код ове функције ће личити на,
// 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); } - Ако погледамо функцију доСометхинг(н), она прихвата параметар по имену н и врши неке прорачуне пре него што поново позове исту процедуру, али са нижим вредностима.
- Када се позове метод доСометхинг() са вредношћу аргумента н, рецимо да Т(н) представља укупну количину времена потребног за завршетак израчунавања. За ово можемо такође формулисати рекурентну релацију, Т(н) = Т(н-1) + К. К овде служи као константа. Константа К је укључена јер је потребно време да функција додели или де-алоцира меморију променљивој или изврши математичку операцију. Користимо К да дефинишемо време јер је тако мало и безначајно.
- Временска сложеност овог рекурзивног програма може се једноставно израчунати пошто се, у најгорем сценарију, метода доСометхинг() позива н пута. Формално говорећи, временска сложеност функције је О(Н).
Трее Рецурсион
- Када извршите рекурзивни позив у свом рекурзивном случају више пута, то се назива рекурзија стабла. Ефикасна илустрација рекурзије дрвета је фибоначијев низ. Рекурзивне функције стабла раде у експоненцијалном времену; нису линеарне по својој временској сложености.
- Погледајте псеудо-код испод,
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); } - Једина разлика између овог кода и претходног је у томе што овај упућује још један позив истој функцији са мањом вредношћу н.
- Ставимо Т(н) = Т(н-1) + Т(н-2) + к као рекурентну релацију за ову функцију. К поново служи као константа.
- Када се изврши више од једног позива исте функције са мањим вредностима, ова врста рекурзије је позната као рекурзија стабла. Интригантан аспект је сада: колико времена одузима ова функција?
- Претпоставите на основу стабла рекурзије испод за исту функцију.
- Можда вам падне на памет да је тешко проценити временску сложеност гледајући директно у рекурзивну функцију, посебно када је у питању рекурзија стабла. Метода стабла рекурзије је једна од неколико техника за израчунавање временске сложености таквих функција. Хајде да га детаљније испитамо.
Шта је метода рекурзивног стабла?
- Рекурзивне релације као што су Т(Н) = Т(Н/2) + Н или две које смо покрили раније у одељцима о врстама рекурзије решавају се коришћењем приступа стабла рекурзије. Ови односи који се понављају често користе стратегију завади па владај за решавање проблема.
- Потребно је време да се интегришу одговори на мање подпроблеме који настају када се већи проблем разбије на мање подпроблеме.
- Релација понављања, на пример, је Т(Н) = 2 * Т(Н/2) + О(Н) за сортирање спајањем. Време потребно да се комбинују одговори на два подпроблема са комбинованом величином Т(Н/2) је О(Н), што је тачно и на нивоу имплементације.
- На пример, пошто је релација понављања за бинарно претраживање Т(Н) = Т(Н/2) + 1, знамо да свака итерација бинарне претраге резултира у простору претраге који је пресечен на пола. Када се одреди исход, излазимо из функције. Релацији понављања је додат +1 јер је ово операција са константним временом.
- Рекурентну релацију Т(н) = 2Т(н/2) + Кн треба размотрити. Кн означава количину времена потребног за комбиновање одговора на н/2-димензионалне подпроблеме.
- Хајде да прикажемо стабло рекурзије за горе поменуту рекурзивну релацију.
Можемо извући неколико закључака из проучавања стабла рекурзије изнад, укључујући
1. Величина проблема на сваком нивоу је све што је битно за одређивање вредности чвора. Величина издања је н на нивоу 0, н/2 на нивоу 1, н/2 на нивоу 2, итд.
2. Генерално, дефинишемо висину стабла као лог (н), где је н величина издања, а висина овог рекурзивног стабла је једнака броју нивоа у стаблу. Ово је тачно јер, као што смо управо установили, стратегија завади па владај се користи у односима понављања за решавање проблема, а прелазак са величине проблема н на величину проблема 1 једноставно захтева предузимање лог (н) корака.
- Размотрите, на пример, вредност Н = 16. Ако нам је дозвољено да поделимо Н са 2 на сваком кораку, колико корака је потребно да бисмо добили Н = 1? С обзиром да у сваком кораку делимо са два, тачан одговор је 4, што је вредност лог(16) базе 2.
лог(16) основа 2
лог(2^4) база 2
4 * лог(2) база 2, пошто је лог(а) база а = 1
дакле, 4 * лог(2) база 2 = 4
3. На сваком нивоу, други члан у понављању се сматра кореном.
Иако се реч „дрво“ појављује у називу ове стратегије, не морате бити стручњак за дрвеће да бисте је разумели.
Како користити стабло рекурзије за решавање рекурзивних односа?
Цена подпроблема у техници стабла рекурзије је количина времена потребног за решавање подпроблема. Стога, ако приметите фразу 'трошак' повезану са стаблом рекурзије, то се једноставно односи на количину времена потребног за решавање одређеног подпроблема.
Хајде да разумемо све ове кораке са неколико примера.
Пример
Размотримо релацију понављања,
Т(н) = 2Т(н/2) + К
Решење
Дата рекурентна релација показује следећа својства,
Проблем величине н је подељен на два подпроблема, сваки величине н/2. Цена комбиновања решења ових подпроблема је К.
ц боолеан
Сваки проблем величине н/2 је подељен на два подпроблема, сваки величине н/4 и тако даље.
На последњем нивоу, величина подпроблема ће бити смањена на 1. Другим речима, коначно смо погодили основни случај.
Хајде да пратимо кораке да решимо ову релацију понављања,
Корак 1: Нацртајте стабло рекурзије
Корак 2: Израчунајте висину дрвета
Пошто знамо да када непрекидно делимо број са 2, долази време када се овај број смањује на 1. Исто као и код величине проблема Н, претпоставимо да након К дељења са 2, Н постане једнако 1, што имплицира, ( н / 2^к) = 1
Овде је н / 2^к величина проблема на последњем нивоу и увек је једнака 1.
Сада можемо лако израчунати вредност к из горњег израза узимајући лог() на обе стране. Испод је јасније извођење,
н = 2^к
- лог(н) = лог(2^к)
- лог(н) = к * лог(2)
- к = лог(н) / лог(2)
- к = лог(н) база 2
Дакле, висина стабла је лог (н) основа 2.
Корак 3: Израчунајте цену на сваком нивоу
- Цена на нивоу-0 = К, два подпроблема су спојена.
- Цена на нивоу-1 = К + К = 2*К, два подпроблема се спајају два пута.
- Цена на нивоу-2 = К + К + К + К = 4*К, два подпроблема се спајају четири пута. и тако даље....
Корак 4: Израчунајте број чворова на сваком нивоу
Хајде да прво одредимо број чворова на последњем нивоу. Из стабла рекурзије ово можемо закључити
- Ниво-0 има 1 (2^0) чвор
- Ниво-1 има 2 (2^1) чвора
- Ниво 2 има 4 (2^2) чвора
- Ниво-3 има 8 (2^3) чворова
Дакле, ниво лог(н) треба да има 2^(лог(н)) чворова, тј. н чворова.
Корак 5: Сумирајте трошкове свих нивоа
- Укупан трошак се може написати као,
- Укупни трошкови = Трошкови свих нивоа осим последњег нивоа + Цена последњег нивоа
- Укупни трошкови = Цена за ниво-0 + Цена за ниво-1 + Цена за ниво-2 +.... + Цена за ниво-лог(н) + Цена за последњи ниво
Цена последњег нивоа се обрачунава посебно јер је то основни случај и на последњем нивоу се не врши спајање, тако да је цена решавања једног проблема на овом нивоу нека константна вредност. Узмимо то као О (1).
Ставимо вредности у формуле,
- Т(н) = К + 2*К + 4*К + .... + лог(н)` пута + `О(1) * н
- Т(н) = К(1 + 2 + 4 + .... + лог(н) пута)` + `О(н)
- Т(н) = К(2^0 + 2^1 + 2^2 + ....+ лог(н) пута + О(н)
Ако пажљиво погледате горњи израз, он формира геометријску прогресију (а, ар, ар^2, ар^3 ...... бесконачно време). Збир ГП је дат са С(Н) = а / (р - 1). Ево првог члана, а р је заједнички однос.