Rekursija yra pagrindinė kompiuterių mokslo ir matematikos sąvoka, leidžianti funkcijoms pasivadinti, o tai leidžia išspręsti sudėtingas problemas iteraciniais žingsniais. Vienas vaizdinis vaizdas, dažniausiai naudojamas norint suprasti ir analizuoti rekursinių funkcijų vykdymą, yra rekursijos medis. Šiame straipsnyje mes išnagrinėsime rekursinių medžių teoriją, jų struktūrą ir reikšmę suprantant rekursinius algoritmus.

Kas yra rekursijos medis?

Rekursijos medis yra grafinis vaizdas, iliustruojantis rekursinės funkcijos vykdymo eigą. Jame pateikiamas vizualinis rekursinių skambučių suskirstymas, parodomas algoritmo progresas, kai jis išsišakoja ir galiausiai pasiekia bazinį atvejį. Medžio struktūra padeda analizuoti laiko sudėtingumą ir suprasti rekursinį procesą.

Medžio struktūra

Kiekvienas rekursijos medžio mazgas reiškia tam tikrą rekursinį skambutį. Pradinis skambutis pavaizduotas viršuje, o po juo išsišakoję vėlesni skambučiai. Medis auga žemyn, sudarydamas hierarchinę struktūrą. Kiekvieno mazgo šakojimosi koeficientas priklauso nuo funkcijos rekursinių skambučių skaičiaus. Be to, medžio gylis atitinka pasikartojančių skambučių skaičių prieš pasiekiant bazinį atvejį.

Bazinis atvejis

Bazinis atvejis naudojamas kaip rekursinės funkcijos pabaigos sąlyga. Jis apibrėžia tašką, kuriame rekursija sustoja ir funkcija pradeda grąžinti reikšmes. Rekursijos medyje mazgai, reprezentuojantys pagrindinį atvejį, paprastai vaizduojami kaip lapų mazgai, nes jie nesukelia tolesnių rekursinių skambučių.

Rekursyvūs skambučiai

Rekursijos medžio antriniai mazgai reiškia rekursinius iškvietimus, atliekamus naudojant funkciją. Kiekvienas antrinis mazgas atitinka atskirą rekursinį skambutį, todėl sukuriamos naujos papildomos problemos. Reikšmės arba parametrai, perduodami šiems rekursiniams skambučiams, gali skirtis, todėl gali skirtis antrinių problemų charakteristikos.

Vykdymo eiga:

Perėjimas per rekursijos medį suteikia įžvalgų apie rekursinės funkcijos vykdymo eigą. Pradėdami nuo pradinio skambučio šakniniame mazge, sekame šakas, kad pasiektume vėlesnius iškvietimus, kol susidursime su baziniu atveju. Pasiekus bazinius atvejus, rekursiniai skambučiai pradeda grįžti, o atitinkami jų mazgai medyje pažymimi grąžintomis reikšmėmis. Perėjimas tęsiamas tol, kol bus perkeltas visas medis.

objektas java

Laiko sudėtingumo analizė

Rekursiniai medžiai padeda analizuoti rekursinių algoritmų sudėtingumą laiku. Išnagrinėję medžio struktūrą, galime nustatyti rekursinių skambučių skaičių ir atliktą darbą kiekviename lygyje. Ši analizė padeda suprasti bendrą algoritmo efektyvumą ir nustatyti galimą neefektyvumą ar optimizavimo galimybes.

Įvadas

• Pagalvokite apie programą, kuri nustato skaičiaus faktorialą. Ši funkcija paima skaičių N kaip įvestį ir kaip rezultatą grąžina N faktorialą. Šios funkcijos pseudokodas bus panašus į

 // 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 */ 

• Rekursijos pavyzdys yra anksčiau minėta funkcija. Skaičiaus faktorialui nustatyti pasitelkiame funkciją. Tada, atsižvelgiant į mažesnę to paties skaičiaus reikšmę, ši funkcija išsikviečia save. Tai tęsiasi tol, kol pasiekiame pagrindinį atvejį, kai nebėra funkcijų iškvietimų.
• Rekursija yra sudėtingų problemų sprendimo technika, kai rezultatas priklauso nuo mažesnių tos pačios problemos atvejų rezultatų.
• Jei galvojame apie funkcijas, sakoma, kad funkcija yra rekursinė, jei ji pati save vadina tol, kol pasiekia bazinę raidę.
• Bet kuri rekursinė funkcija turi du pagrindinius komponentus: bazinį atvejį ir rekursinį žingsnį. Pasiekę pagrindinį atvejį, nustojame pereiti į rekursinę fazę. Siekiant išvengti nesibaigiančios pasikartojimo, baziniai atvejai turi būti tinkamai apibrėžti ir yra labai svarbūs. Begalinės rekursijos apibrėžimas yra rekursija, kuri niekada nepasiekia bazinio atvejo. Jei programa niekada nepasieks bazinio atvejo, dėklo perpildymas ir toliau vyks.

Rekursijos tipai

Apskritai, yra dvi skirtingos rekursijos formos:

• Tiesinė rekursija
• Medžio rekursija
• Tiesinė rekursija

Tiesinė rekursija

• Funkcija, kuri kiekvieną kartą ją vykdant išsikviečia tik vieną kartą, yra tiesiškai rekursinė. Puiki tiesinės rekursijos iliustracija yra faktorinė funkcija. Pavadinimas „tiesinė rekursija“ reiškia faktą, kad tiesiškai rekursinei funkcijai vykdyti reikia linijinio laiko.
• Pažvelkite į toliau pateiktą pseudo kodą:

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

• Jei pažvelgsime į funkciją doSomething(n), ji priima parametrą pavadinimu n ir atlieka kai kuriuos skaičiavimus prieš dar kartą iškviesdama tą pačią procedūrą, bet su mažesnėmis reikšmėmis.
• Kai metodas doSomething() iškviečiamas su argumento reikšme n, tarkime, kad T(n) reiškia visą laiką, reikalingą skaičiavimui užbaigti. Tam taip pat galime suformuluoti pasikartojimo ryšį, T(n) = T(n-1) + K. K čia yra konstanta. Konstanta K įtraukta, nes užtrunka, kol funkcija paskirsto atmintį arba panaikina jo paskirstymą kintamajam arba atlieka matematinę operaciją. Naudojame K, norėdami apibrėžti laiką, nes jis yra toks trumpas ir nereikšmingas.
• Šios rekursinės programos laiko sudėtingumas gali būti tiesiog apskaičiuojamas, nes blogiausiu atveju metodas doSomething() iškviečiamas n kartų. Formaliai kalbant, funkcijos laikinasis sudėtingumas yra O(N).

Medžio rekursija

• Kai atliekate rekursinį skambutį rekursiniu atveju daugiau nei vieną kartą, tai vadinama medžio rekursija. Veiksminga medžio rekursijos iliustracija yra fibonačio seka. Medžio rekursinės funkcijos veikia eksponentiniu laiku; jie nėra linijiniai savo laikinu sudėtingumu.
• Pažvelkite į žemiau esantį pseudo kodą,

 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); } 

• Vienintelis skirtumas tarp šio kodo ir ankstesnio yra tas, kad šis dar vieną kartą iškviečia tą pačią funkciją su mažesne n reikšme.
• Įdėkime T(n) = T(n-1) + T(n-2) + k kaip šios funkcijos pasikartojimo ryšį. K dar kartą tarnauja kaip konstanta.
• Kai atliekamas daugiau nei vienas iškvietimas į tą pačią funkciją su mažesnėmis reikšmėmis, tokio tipo rekursija vadinama medžio rekursija. Intriguojantis aspektas dabar yra toks: kiek laiko atima ši funkcija?
• Remdamiesi toliau pateiktu tos pačios funkcijos rekursijos medžiu, spėkite.
  
• Jums gali pasirodyti, kad sunku įvertinti laiko sudėtingumą žiūrint tiesiai į rekursinę funkciją, ypač kai tai yra medžio rekursija. Rekursijos medžio metodas yra vienas iš kelių metodų, skirtų tokių funkcijų laikinajam sudėtingumui apskaičiuoti. Panagrinėkime tai išsamiau.

Kas yra rekursijos medžio metodas?

• Pasikartojimo ryšiai, tokie kaip T(N) = T(N/2) + N arba du, kuriuos aptarėme anksčiau rekursijos tipų skyriuje, išsprendžiami naudojant rekursijos medžio metodą. Šie pasikartojantys santykiai dažnai naudoja „skaldyk ir valdyk“ strategiją problemoms spręsti.
• Atsakymams į smulkesnes problemas, atsirandančias, kai didesnė problema suskaidoma į mažesnes problemas, reikia laiko integruoti.
• Pavyzdžiui, pasikartojimo ryšys yra T(N) = 2 * T(N/2) + O(N) sujungimo rūšiavimui. Laikas, reikalingas dviejų papildomų problemų, kurių bendras dydis yra T(N/2), atsakymams sujungti, yra O(N), o tai taip pat galioja įgyvendinimo lygmeniu.
• Pavyzdžiui, kadangi dvejetainės paieškos pasikartojimo santykis yra T(N) = T(N/2) + 1, žinome, kad kiekviena dvejetainės paieškos iteracija lemia paieškos erdvę, kuri yra perpjauta per pusę. Nustačius rezultatą, išeiname iš funkcijos. Pasikartojimo ryšys pridėtas +1, nes tai yra pastovaus laiko operacija.
• Reikia atsižvelgti į pasikartojimo ryšį T(n) = 2T(n/2) + Kn. Kn žymi laiką, reikalingą n/2 matmenų poproblemų atsakymams sujungti.
• Pavaizduokime anksčiau minėto pasikartojimo santykio rekursijos medį.

Ištyrę aukščiau pateiktą rekursijos medį galime padaryti keletą išvadų, įskaitant

1. Problemos dydis kiekviename lygyje yra viskas, kas svarbu nustatant mazgo vertę. Išleidimo dydis yra n 0 lygiu, n/2 1 lygiu, n/2 2 lygiu ir pan.

2. Apskritai medžio aukštį apibrėžiame kaip logą (n), kur n yra problemos dydis, o šio rekursinio medžio aukštis lygus medžio lygių skaičiui. Tai tiesa, nes, kaip ką tik nustatėme, „skaldyk ir valdyk“ strategiją pasikartojantys ryšiai naudoja problemoms spręsti, o norint pereiti nuo n dydžio iki problemos dydžio 1, tiesiog reikia atlikti log (n) žingsnius.

• Apsvarstykite, pavyzdžiui, reikšmę N = 16. Jei kiekviename žingsnyje mums leidžiama padalyti N iš 2, kiek žingsnių reikia, kad gautume N = 1? Atsižvelgiant į tai, kad kiekviename žingsnyje dalijame iš dviejų, teisingas atsakymas yra 4, tai yra log(16) bazės 2 reikšmė.

log(16) bazė 2

log(2^4) 2 bazė

4 * log(2) bazė 2, nes log(a) bazė a = 1

len of string java

taigi, 4 * log(2) bazė 2 = 4

3. Kiekviename lygyje antrasis pasikartojimo terminas laikomas šaknimis.

Nors šios strategijos pavadinime yra žodis „medis“, jums nereikia būti medžių ekspertu, kad jį suprastumėte.

Kaip naudoti rekursijos medį pasikartojimo ryšiams išspręsti?

Papildomos problemos kaina rekursijos medžio technikoje yra laikas, reikalingas antrinei problemai išspręsti. Todėl, jei pastebėjote su rekursijos medžiu susietą frazę „kaina“, tai tiesiog nurodo laiką, reikalingą tam tikrai antrinei problemai išspręsti.

Supraskime visus šiuos veiksmus pateikdami kelis pavyzdžius.

Pavyzdys

Apsvarstykite pasikartojimo ryšį,

kampinė medžiaga

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

Sprendimas

Pateiktas pasikartojimo ryšys parodo šias savybes,

N dydžio uždavinys yra padalintas į dvi dalis, kurių kiekvienos dydis yra n/2. Šių poproblemų sprendimų derinimo kaina yra K.

Kiekvienas n/2 uždavinio dydis yra padalintas į dvi dalis, kurių kiekviena yra n/4 dydžio ir pan.

Paskutiniame lygyje antrinės problemos dydis bus sumažintas iki 1. Kitaip tariant, pagaliau pasiekėme pagrindinį atvejį.

Atlikime veiksmus, kad išspręstume šį pasikartojimo ryšį,

1 veiksmas: nubrėžkite rekursijos medį

2 veiksmas: apskaičiuokite medžio aukštį

Kadangi žinome, kad kai nuolat dalijame skaičių iš 2, ateina laikas, kai šis skaičius sumažinamas iki 1. Taip pat, kaip ir problemos dydžiui N, tarkime, po K dalijimo iš 2, N tampa lygus 1, o tai reiškia, ( n / 2^k) = 1

mašinraščio rinkinys

Čia n / 2^k yra problemos dydis paskutiniame lygyje ir visada lygus 1.

Dabar galime lengvai apskaičiuoti k reikšmę iš aukščiau pateiktos išraiškos, paimdami log() į abi puses. Žemiau pateikiamas aiškesnis išvedimas,

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) 2 bazė

Taigi medžio aukštis yra log (n) bazė 2.

3 veiksmas: apskaičiuokite kiekvieno lygio išlaidas

• Kaina lygiu-0 = K, sujungiamos dvi poproblemos.
• Kaina 1 lygyje = K + K = 2*K, dvi poproblemos sujungiamos du kartus.
• Kaina 2 lygyje = K + K + K + K = 4*K, dvi poproblemos sujungiamos keturis kartus. ir taip toliau....

4 veiksmas: apskaičiuokite mazgų skaičių kiekviename lygyje

Pirmiausia nustatykime mazgų skaičių paskutiniame lygyje. Iš rekursijos medžio galime tai padaryti

c kodo eilučių masyvas

• 0 lygis turi 1 (2^0) mazgą
• 1 lygis turi 2 (2^1) mazgus
• 2 lygis turi 4 (2^2) mazgus
• 3 lygis turi 8 (2^3) mazgus

Taigi lygio log(n) turėtų turėti 2^(log(n)) mazgų, ty n mazgų.

5 veiksmas: susumuokite visų lygių kainą

• Bendra kaina gali būti parašyta kaip
• Bendra kaina = visų lygių, išskyrus paskutinį lygį, kaina + paskutinio lygio kaina
• Bendra kaina = 0 lygio kaina + 1 lygio kaina + 2 lygio kaina +.... + Log(n) lygio kaina + paskutinio lygio kaina

Paskutinio lygio kaina apskaičiuojama atskirai, nes tai yra bazinis atvejis ir paskutiniame lygyje sujungimas nevykdomas, todėl vienos problemos sprendimo šiame lygyje kaina yra tam tikra pastovi vertė. Paimkime tai kaip O (1).

Sudėkime reikšmes į formules,

• T(n) = K + 2*K + 4*K + .... + log(n)' kartus + 'O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) kartus)' + 'O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) kartus + O(n)

Jei atidžiai pažvelgsite į aukščiau pateiktą išraišką, ji sudaro geometrinę progresiją (a, ar, ar^2, ar^3 ...... begalinis laikas). GP suma pateikiama S(N) = a / (r - 1). Čia yra pirmasis narys, o r yra bendras santykis.