Rekurzija je temeljni koncept v računalništvu in matematiki, ki omogoča funkcijam, da pokličejo same sebe, kar omogoča reševanje kompleksnih problemov s ponavljajočimi se koraki. Ena vizualna predstavitev, ki se običajno uporablja za razumevanje in analizo izvajanja rekurzivnih funkcij, je rekurzijsko drevo. V tem članku bomo raziskali teorijo, ki stoji za rekurzivnimi drevesi, njihovo strukturo in njihov pomen pri razumevanju rekurzivnih algoritmov.

Kaj je rekurzijsko drevo?

Rekurzijsko drevo je grafična predstavitev, ki ponazarja potek izvajanja rekurzivne funkcije. Zagotavlja vizualno razčlenitev rekurzivnih klicev, ki prikazuje napredovanje algoritma, ko se razveja in na koncu doseže osnovni primer. Drevesna struktura pomaga pri analizi časovne kompleksnosti in razumevanju vključenega rekurzivnega procesa.

Drevesna struktura

Vsako vozlišče v rekurzivnem drevesu predstavlja določen rekurziven klic. Začetni klic je prikazan na vrhu, naslednji klici pa se razvejajo pod njim. Drevo raste navzdol in tvori hierarhično strukturo. Faktor razvejanja vsakega vozlišča je odvisen od števila rekurzivnih klicev znotraj funkcije. Poleg tega globina drevesa ustreza številu rekurzivnih klicev, preden doseže osnovni primer.

Osnovni primer

Osnovni primer služi kot zaključni pogoj za rekurzivno funkcijo. Določa točko, na kateri se rekurzija ustavi in ​​funkcija začne vračati vrednosti. V rekurzivnem drevesu so vozlišča, ki predstavljajo osnovni primer, običajno prikazana kot listna vozlišča, saj ne povzročijo nadaljnjih rekurzivnih klicev.

stikalo za tipkopis

Rekurzivni klici

Podrejena vozlišča v rekurzivnem drevesu predstavljajo rekurzivne klice znotraj funkcije. Vsako podrejeno vozlišče ustreza ločenemu rekurzivnemu klicu, kar ima za posledico ustvarjanje novih podproblemov. Vrednosti ali parametri, posredovani tem rekurzivnim klicem, se lahko razlikujejo, kar povzroči razlike v značilnostih podproblemov.

Potek izvajanja:

Prečkanje rekurzivnega drevesa nudi vpogled v tok izvajanja rekurzivne funkcije. Začenši od začetnega klica v korenskem vozlišču, sledimo vejam, da dosežemo naslednje klice, dokler ne naletimo na osnovni primer. Ko so doseženi osnovni primeri, se rekurzivni klici začnejo vračati, njihova ustrezna vozlišča v drevesu pa so označena z vrnjenimi vrednostmi. Prehod se nadaljuje, dokler ni prečkano celotno drevo.

Analiza časovne kompleksnosti

Rekurzivna drevesa pomagajo pri analizi časovne kompleksnosti rekurzivnih algoritmov. S preučevanjem strukture drevesa lahko ugotovimo število opravljenih rekurzivnih klicev in opravljeno delo na vsaki ravni. Ta analiza pomaga pri razumevanju splošne učinkovitosti algoritma in prepoznavanju morebitnih neučinkovitosti ali priložnosti za optimizacijo.

Uvod

• Pomislite na program, ki določa faktoriel števila. Ta funkcija sprejme število N kot vhod in kot rezultat vrne faktoriel N. Psevdo koda te funkcije bo podobna,

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

• Rekurzijo ponazarja funkcija, ki je bila prej omenjena. Prikličemo funkcijo za določitev faktoriala števila. Potem, glede na manjšo vrednost istega števila, ta funkcija pokliče samo sebe. To se nadaljuje, dokler ne pridemo do osnovnega primera, v katerem ni več klicev funkcij.
• Rekurzija je tehnika za obravnavo zapletenih težav, ko je rezultat odvisen od rezultatov manjših primerkov iste težave.
• Če razmišljamo o funkcijah, rečemo, da je funkcija rekurzivna, če kliče samo sebe, dokler ne doseže osnovnega primera.
• Vsaka rekurzivna funkcija ima dve glavni komponenti: osnovni primer in rekurzivni korak. Ko pridemo do osnovnega primera, prenehamo z rekurzivno fazo. Da bi preprečili neskončno ponavljanje, morajo biti osnovni primeri pravilno definirani in so ključni. Definicija neskončne rekurzije je rekurzija, ki nikoli ne doseže osnovnega primera. Če program nikoli ne doseže osnovnega primera, bo še naprej prihajalo do prelivanja sklada.

Vrste rekurzij

Na splošno obstajata dve različni obliki rekurzije:

• Linearna rekurzija
• Drevesna rekurzija
• Linearna rekurzija

Linearna rekurzija

• Funkcija, ki se pri vsaki izvedbi samo enkrat pokliče, se imenuje linearno rekurzivna. Lepa ilustracija linearne rekurzije je faktorialna funkcija. Ime 'linearna rekurzija' se nanaša na dejstvo, da linearno rekurzivna funkcija potrebuje linearno količino časa za izvedbo.
• Oglejte si spodnjo psevdo kodo:

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

• Če pogledamo funkcijo doSomething(n), ta sprejme parameter z imenom n in opravi nekaj izračunov, preden ponovno pokliče isti postopek, vendar z nižjimi vrednostmi.
• Ko je metoda doSomething() poklicana z vrednostjo argumenta n, recimo, da T(n) predstavlja skupno količino časa, ki je potreben za dokončanje izračuna. Za to lahko formuliramo tudi povratno razmerje, T(n) = T(n-1) + K. K tukaj služi kot konstanta. Konstanta K je vključena, ker funkcija potrebuje čas, da dodeli ali sprosti pomnilnik spremenljivki ali izvede matematično operacijo. Za določitev časa uporabljamo K, saj je tako majhen in nepomemben.
• Časovno kompleksnost tega rekurzivnega programa je mogoče preprosto izračunati, saj je v najslabšem scenariju metoda doSomething() poklicana n-krat. Formalno gledano je časovna kompleksnost funkcije O(N).

Drevesna rekurzija

• Ko izvedete rekurzivni klic v svojem rekurzivnem primeru več kot enkrat, se to imenuje drevesna rekurzija. Učinkovita ilustracija drevesne rekurzije je fibonaccijevo zaporedje. Drevesne rekurzivne funkcije delujejo v eksponentnem času; v svoji časovni kompleksnosti niso linearni.
• Oglejte si spodnjo psevdokodo,

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

• Edina razlika med to kodo in prejšnjo je, da ta izvede še en klic iste funkcije z nižjo vrednostjo n.
• Vstavimo T(n) = T(n-1) + T(n-2) + k kot povratno razmerje za to funkcijo. K spet služi kot konstanta.
• Ko se izvede več kot en klic iste funkcije z manjšimi vrednostmi, je ta vrsta rekurzije znana kot drevesna rekurzija. Intriganten vidik je zdaj: kako dolgotrajna je ta funkcija?
• Ugibajte na podlagi spodnjega drevesa rekurzije za isto funkcijo.
  
• Morda se vam zdi, da je težko oceniti časovno kompleksnost z neposrednim pogledom na rekurzivno funkcijo, zlasti če gre za drevesno rekurzijo. Metoda rekurzijskega drevesa je ena od več tehnik za izračun časovne kompleksnosti takih funkcij. Preučimo ga podrobneje.

Kaj je metoda rekurzijskega drevesa?

• Ponavljajoče se relacije, kot je T(N) = T(N/2) + N ali dve, ki smo ju obravnavali prej v razdelku o vrstah rekurzije, se rešujejo s pristopom rekurzijskega drevesa. Ti ponavljajoči se odnosi pogosto uporabljajo strategijo deli in vladaj za reševanje težav.
• Potreben je čas za integracijo odgovorov na manjše podprobleme, ki nastanejo, ko se večji problem razdeli na manjše podprobleme.
• Rekurenčna relacija je na primer T(N) = 2 * T(N/2) + O(N) za razvrščanje z združitvijo. Čas, potreben za združevanje odgovorov na dve podproblemi s skupno velikostjo T(N/2) je O(N), kar velja tudi na ravni izvedbe.
• Na primer, ker je povratna relacija za binarno iskanje T(N) = T(N/2) + 1, vemo, da vsaka ponovitev binarnega iskanja povzroči iskalni prostor, ki je prepolovljen. Ko je rezultat določen, zapustimo funkcijo. Relaciji ponavljanja je dodan +1, ker je to operacija s konstantnim časom.
• Upoštevati je treba povratno razmerje T(n) = 2T(n/2) + Kn. Kn označuje čas, potreben za združevanje odgovorov na n/2-dimenzionalne podprobleme.
• Upodabljajmo rekurzijsko drevo za prej omenjeno povratno relacijo.

Iz preučevanja zgornjega rekurzijskega drevesa lahko potegnemo nekaj zaključkov, vključno z

1. Velikost problema na vsaki ravni je vse, kar je pomembno za določitev vrednosti vozlišča. Velikost izdaje je n na ravni 0, n/2 na ravni 1, n/2 na ravni 2 itd.

2. Na splošno definiramo višino drevesa, ki je enaka log (n), kjer je n velikost problema, višina tega rekurzijskega drevesa pa je enaka številu ravni v drevesu. To je res, ker, kot smo pravkar ugotovili, se strategija deli in vladaj uporablja s ponavljajočimi se odnosi za reševanje problemov, prehod od velikosti problema n do velikosti problema 1 pa preprosto zahteva dnevnik (n) korakov.

• Upoštevajte na primer vrednost N = 16. Če nam je dovoljeno deliti N z 2 v vsakem koraku, koliko korakov je potrebnih, da dobimo N = 1? Glede na to, da na vsakem koraku delimo z dve, je pravilen odgovor 4, kar je vrednost log(16) osnove 2.

log(16) osnova 2

log(2^4) osnova 2

4 * log(2) osnova 2, ker je log(a) osnova a = 1

torej 4 * log(2) osnova 2 = 4

3. Na vsaki ravni se drugi člen v ponovitvi obravnava kot koren.

Čeprav se v imenu te strategije pojavlja beseda 'drevo', vam ni treba biti strokovnjak za drevesa, da bi jo razumeli.

Kako uporabiti rekurzijsko drevo za reševanje ponavljajočih se relacij?

Stroški podproblema v tehniki rekurzijskega drevesa so čas, potreben za rešitev podproblema. Če torej opazite besedno zvezo 'strošek', povezano z rekurzijskim drevesom, se preprosto nanaša na količino časa, potrebnega za rešitev določenega podproblema.

Razumejmo vse te korake z nekaj primeri.

Primer

Razmislite o ponovitvenem razmerju,

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

rešitev

Podana povratna relacija kaže naslednje lastnosti,

Problem velikosti n je razdeljen na dva podproblema velikosti n/2. Stroški združevanja rešitev teh podproblemov so K.

Vsak problem velikosti n/2 je razdeljen na dva podproblema velikosti n/4 in tako naprej.

Na zadnji ravni se bo velikost podproblema zmanjšala na 1. Z drugimi besedami, končno smo dosegli osnovni primer.

Sledimo korakom za rešitev te relacije ponavljanja,

1. korak: Narišite rekurzijsko drevo

2. korak: Izračunajte višino drevesa

Ker vemo, da ko število neprekinjeno delimo z 2, pride čas, ko se to število zmanjša na 1. Enako kot pri velikosti problema N, predpostavimo, da po K delitvah z 2 postane N enako 1, kar pomeni, ( n / 2^k) = 1

Tukaj je n / 2^k velikost problema na zadnji ravni in je vedno enaka 1.

Zdaj lahko preprosto izračunamo vrednost k iz zgornjega izraza tako, da vzamemo log() na obe strani. Spodaj je bolj jasna izpeljava,

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) osnova 2

Torej je višina drevesa log (n) osnova 2.

3. korak: Izračunajte stroške na vsaki ravni

• Strošek na ravni 0 = K, dva podproblema sta združena.
• Stroški na ravni-1 = K + K = 2*K, dva podproblema sta dvakrat združena.
• Stroški na ravni-2 = K + K + K + K = 4*K, dva podproblema sta štirikrat združena. in tako naprej....

4. korak: Izračunajte število vozlišč na vsaki ravni

Najprej določimo število vozlišč v zadnjem nivoju. Iz rekurzijskega drevesa lahko to sklepamo

• Raven-0 ima 1 (2^0) vozlišče
• Raven-1 ima 2 (2^1) vozlišča
• Raven-2 ima 4 (2^2) vozlišča
• Raven-3 ima 8 (2^3) vozlišč

Torej bi moral imeti nivo log(n) 2^(log(n)) vozlišč, tj. n vozlišč.

5. korak: Seštejte stroške vseh stopenj

kako nadgraditi javo

• Skupne stroške lahko zapišemo kot
• Skupni strošek = strošek vseh stopenj razen zadnje stopnje + strošek zadnje stopnje
• Skupni strošek = strošek za stopnjo-0 + strošek za raven-1 + strošek za raven-2 +.... + strošek za raven-log(n) + strošek za zadnjo stopnjo

Stroški zadnje ravni se izračunajo ločeno, ker je to osnovni primer in na zadnji ravni ni združevanja, tako da je cena za rešitev posameznega problema na tej ravni neka stalna vrednost. Vzemimo ga kot O (1).

Vstavimo vrednosti v formule,

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

Če pozorno pogledate zgornji izraz, tvori geometrijsko progresijo (a, ar, ar^2, ar^3 ...... neskončen čas). Vsota GP je podana z S(N) = a / (r - 1). Tukaj je prvi člen in r je običajno razmerje.