Rekurzija je temeljni koncept u računalnoj znanosti i matematici koji omogućuje funkcijama da same sebe pozivaju, omogućujući rješavanje složenih problema kroz iterativne korake. Jedan vizualni prikaz koji se obično koristi za razumijevanje i analizu izvršenja rekurzivnih funkcija je rekurzijsko stablo. U ovom ćemo članku istražiti teoriju koja stoji iza rekurzijskih stabala, njihovu strukturu i njihov značaj u razumijevanju rekurzivnih algoritama.

Što je rekurzijsko stablo?

Rekurzivno stablo je grafički prikaz koji ilustrira tijek izvršenja rekurzivne funkcije. Omogućuje vizualnu raščlambu rekurzivnih poziva, prikazujući napredak algoritma kako se grana i na kraju doseže osnovni slučaj. Struktura stabla pomaže u analizi vremenske složenosti i razumijevanju uključenog rekurzivnog procesa.

Struktura stabla

Svaki čvor u stablu rekurzije predstavlja određeni rekurzivni poziv. Početni poziv prikazan je na vrhu, dok se kasniji pozivi granaju ispod njega. Stablo raste prema dolje, tvoreći hijerarhijsku strukturu. Faktor grananja svakog čvora ovisi o broju rekurzivnih poziva unutar funkcije. Dodatno, dubina stabla odgovara broju rekurzivnih poziva prije dostizanja osnovnog slučaja.

Osnovni slučaj

Osnovni slučaj služi kao terminacijski uvjet za rekurzivnu funkciju. Definira točku u kojoj se rekurzija zaustavlja i funkcija počinje vraćati vrijednosti. U stablu rekurzije, čvorovi koji predstavljaju osnovni slučaj obično su prikazani kao čvorovi listova, budući da ne rezultiraju daljnjim rekurzivnim pozivima.

Rekurzivni pozivi

Podređeni čvorovi u stablu rekurzije predstavljaju rekurzivne pozive unutar funkcije. Svaki podređeni čvor odgovara zasebnom rekurzivnom pozivu, što rezultira stvaranjem novih podproblema. Vrijednosti ili parametri proslijeđeni ovim rekurzivnim pozivima mogu se razlikovati, što dovodi do varijacija u karakteristikama podproblema.

Tijek izvršenja:

Prelazak rekurzivnog stabla pruža uvid u tijek izvršenja rekurzivne funkcije. Počevši od početnog poziva u korijenskom čvoru, pratimo grane kako bismo došli do sljedećih poziva sve dok ne naiđemo na osnovni slučaj. Kako se dosegnu osnovni slučajevi, rekurzivni pozivi počinju se vraćati, a njihovi čvorovi u stablu označeni su vraćenim vrijednostima. Obilaženje se nastavlja dok se ne prijeđe cijelo stablo.

Analiza vremenske složenosti

Rekurzivna stabla pomažu u analizi vremenske složenosti rekurzivnih algoritama. Ispitivanjem strukture stabla možemo odrediti broj rekurzivnih poziva i obavljen posao na svakoj razini. Ova analiza pomaže u razumijevanju ukupne učinkovitosti algoritma i identificiranju potencijalnih neučinkovitosti ili prilika za optimizaciju.

Uvod

• Zamislite program koji određuje faktorijel broja. Ova funkcija uzima broj N kao ulaz i vraća faktorijel od N kao rezultat. Pseudokod ove funkcije sličit će,

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

• Primjer rekurzije je funkcija koja je prethodno spomenuta. Pozivamo funkciju za određivanje faktorijela broja. Zatim, s obzirom na manju vrijednost istog broja, ova funkcija poziva samu sebe. To se nastavlja sve dok ne dođemo do osnovnog slučaja, u kojem više nema poziva funkcija.
• Rekurzija je tehnika za rješavanje kompliciranih problema kada ishod ovisi o ishodima manjih instanci istog problema.
• Ako razmišljamo o funkcijama, za funkciju se kaže da je rekurzivna ako nastavlja pozivati ​​samu sebe dok ne dosegne osnovni slučaj.
• Svaka rekurzivna funkcija ima dvije primarne komponente: osnovni slučaj i rekurzivni korak. Prestajemo ići u rekurzivnu fazu kada dođemo do osnovnog slučaja. Kako bi se spriječila beskrajna rekurzija, osnovni slučajevi moraju biti pravilno definirani i ključni su. Definicija beskonačne rekurzije je rekurzija koja nikada ne doseže osnovni slučaj. Ako program nikad ne dostigne osnovni slučaj, prelijevanje stoga će se i dalje događati.

Vrste rekurzije

Općenito govoreći, postoje dva različita oblika rekurzije:

• Linearna rekurzija
• Rekurzija stabla
• Linearna rekurzija

Linearna rekurzija

• Za funkciju koja samu sebe poziva samo jednom prilikom svakog izvršavanja kaže se da je linearno rekurzivna. Lijepa ilustracija linearne rekurzije je faktorijelna funkcija. Naziv 'linearna rekurzija' odnosi se na činjenicu da linearno rekurzivnoj funkciji treba linearna količina vremena da se izvrši.
• Pogledajte pseudo kod u nastavku:

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

• Ako pogledamo funkciju doSomething(n), ona prihvaća parametar pod nazivom n i radi neke izračune prije ponovnog pozivanja iste procedure, ali s nižim vrijednostima.
• Kada se metoda doSomething() pozove s vrijednošću argumenta n, recimo da T(n) predstavlja ukupno vrijeme potrebno za dovršetak izračuna. U tu svrhu također možemo formulirati odnos ponavljanja, T(n) = T(n-1) + K. K ovdje služi kao konstanta. Konstanta K je uključena jer je potrebno vrijeme da funkcija dodijeli ili dealocira memoriju varijabli ili izvede matematičku operaciju. Koristimo K da definiramo vrijeme budući da je ono tako sićušno i beznačajno.
• Vremenska složenost ovog rekurzivnog programa može se jednostavno izračunati jer se, u najgorem scenariju, metoda doSomething() poziva n puta. Formalno govoreći, vremenska složenost funkcije je O(N).

Rekurzija stabla

• Kada napravite rekurzivni poziv u svom rekurzivnom slučaju više od jednom, to se naziva rekurzija stabla. Učinkovita ilustracija rekurzije stabla je fibonaccijev niz. Rekurzivne funkcije stabla rade u eksponencijalnom vremenu; oni nisu linearni u svojoj vremenskoj složenosti.
• Pogledajte pseudo-kod ispod,

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

• Jedina razlika između ovog koda i prethodnog je što ovaj upućuje još jedan poziv na istu funkciju s nižom vrijednošću n.
• Stavimo T(n) = T(n-1) + T(n-2) + k kao relaciju ponavljanja za ovu funkciju. K opet služi kao konstanta.
• Kada se izvrši više od jednog poziva iste funkcije s manjim vrijednostima, ova vrsta rekurzije poznata je kao rekurzija stabla. Intrigantan aspekt je sada: koliko vremena oduzima ova funkcija?
• Pogodite na temelju stabla rekurzije u nastavku za istu funkciju.
  
• Može vam se dogoditi da je izazovno procijeniti vremensku složenost gledajući izravno na rekurzivnu funkciju, osobito kada je to rekurzija stabla. Metoda rekurzivnog stabla jedna je od nekoliko tehnika za izračunavanje vremenske složenosti takvih funkcija. Ispitajmo ga detaljnije.

Što je metoda rekurzivnog stabla?

• Relacije ponavljanja kao što su T(N) = T(N/2) + N ili dvije koje smo ranije obradili u odjeljku o vrstama rekurzije rješavaju se pristupom stabla rekurzije. Ovi odnosi koji se ponavljaju često koriste strategiju zavadi pa vladaj za rješavanje problema.
• Potrebno je vrijeme da se integriraju odgovori na manje podprobleme koji nastaju kada se veći problem podijeli na manje podprobleme.
• Relacija ponavljanja je, na primjer, T(N) = 2 * T(N/2) + O(N) za sortiranje spajanjem. Vrijeme potrebno za kombiniranje odgovora na dva podproblema s kombiniranom veličinom T(N/2) je O(N), što vrijedi i na razini implementacije.
• Na primjer, budući da je relacija ponavljanja za binarno pretraživanje T(N) = T(N/2) + 1, znamo da svaka iteracija binarnog pretraživanja rezultira prostorom za pretraživanje koji je prepolovljen. Nakon što je rezultat određen, izlazimo iz funkcije. Relaciji ponavljanja dodan je +1 jer je ovo operacija s konstantnim vremenom.
• Treba uzeti u obzir relaciju ponavljanja T(n) = 2T(n/2) + Kn. Kn označava količinu vremena potrebnog za kombiniranje odgovora na n/2-dimenzionalne podprobleme.
• Oslikajmo stablo rekurzije za gore spomenutu relaciju ponavljanja.

Možemo izvući nekoliko zaključaka iz proučavanja gornjeg stabla rekurzije, uključujući

1. Veličina problema na svakoj razini je sve što je bitno za određivanje vrijednosti čvora. Veličina izdanja je n na razini 0, n/2 na razini 1, n/2 na razini 2 itd.

2. Općenito, definiramo visinu stabla kao jednaku log (n), gdje je n veličina izdanja, a visina ovog rekurzivnog stabla jednaka je broju razina u stablu. To je istina jer, kao što smo upravo ustanovili, strategija zavadi-pa-vladaj koristi se relacijama ponavljanja za rješavanje problema, a prelazak s veličine problema n na veličinu problema 1 jednostavno zahtijeva poduzimanje log (n) koraka.

• Razmotrimo, na primjer, vrijednost N = 16. Ako nam je dopušteno podijeliti N s 2 u svakom koraku, koliko je koraka potrebno da dobijemo N = 1? Uzimajući u obzir da u svakom koraku dijelimo s dva, točan odgovor je 4, što je vrijednost log(16) baze 2.

log(16) baza 2

log(2^4) baza 2

4 * log(2) baza 2, budući da je log(a) baza a = 1

dakle, 4 * log(2) baza 2 = 4

3. Na svakoj razini, drugi član u ponavljanju se smatra korijenom.

Iako se u nazivu ove strategije pojavljuje riječ 'drvo', ne morate biti stručnjak za drveće da biste to razumjeli.

c++ int u niz

Kako koristiti stablo rekurzije za rješavanje relacija ponavljanja?

Trošak podproblema u tehnici rekurzivnog stabla je količina vremena potrebnog za rješavanje podproblema. Stoga, ako primijetite izraz 'trošak' povezan s rekurzijskom stablom, on se jednostavno odnosi na količinu vremena potrebnog za rješavanje određenog podproblema.

Razjasnimo sve ove korake uz nekoliko primjera.

Primjer

Razmotrimo odnos ponavljanja,

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

Riješenje

Dana relacija ponavljanja pokazuje sljedeća svojstva,

Problem veličine n podijeljen je na dva podproblema veličine n/2. Trošak kombiniranja rješenja ovih podproblema je K.

Svaki problem veličine n/2 podijeljen je u dva podproblema veličine n/4 i tako dalje.

Na posljednjoj razini, veličina podproblema će se smanjiti na 1. Drugim riječima, konačno smo pogodili osnovni slučaj.

Slijedimo korake za rješavanje ove relacije ponavljanja,

sortiranje java polja

Korak 1: Nacrtajte rekurzijsko stablo

Korak 2: Izračunajte visinu stabla

Budući da znamo da kada kontinuirano dijelimo broj s 2, dolazi trenutak kada se taj broj smanjuje na 1. Isto kao i s veličinom problema N, pretpostavimo da nakon K dijeljenja s 2, N postaje jednako 1, što implicira, ( n / 2^k) = 1

Ovdje je n / 2^k veličina problema na posljednjoj razini i uvijek je jednaka 1.

Sada možemo jednostavno izračunati vrijednost k iz gornjeg izraza uzimajući log() na obje strane. Ispod je jasnija derivacija,

n = 2^k

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

Dakle, visina stabla je log (n) baze 2.

Korak 3: Izračunajte trošak na svakoj razini

• Trošak na razini-0 = K, dva podproblema su spojena.
• Trošak na razini-1 = K + K = 2*K, dva podproblema se spajaju dva puta.
• Trošak na razini-2 = K + K + K + K = 4*K, dva podproblema se spajaju četiri puta. i tako dalje....

Korak 4: Izračunajte broj čvorova na svakoj razini

Prvo odredimo broj čvorova u posljednjoj razini. To možemo zaključiti iz stabla rekurzije

• Razina-0 ima 1 (2^0) čvor
• Razina-1 ima 2 (2^1) čvora
• Razina-2 ima 4 (2^2) čvora
• Razina-3 ima 8 (2^3) čvorova

Dakle, log(n) razine treba imati 2^(log(n)) čvorova, tj. n čvorova.

Korak 5: Zbrojite troškove svih razina

• Ukupni trošak može se napisati kao,
• Ukupni trošak = trošak svih razina osim zadnje razine + trošak posljednje razine
• Ukupni trošak = Trošak za nivo-0 + Trošak za nivo-1 + Trošak za nivo-2 +.... + Trošak za nivo-log(n) + Trošak za posljednju razinu

Trošak posljednje razine izračunava se zasebno jer je to osnovni slučaj i na posljednjoj razini se ne vrši spajanje, tako da je cijena rješavanja jednog problema na ovoj razini neka konstantna vrijednost. Uzmimo to kao O (1).

Stavimo vrijednosti u formule,

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

Ako pažljivo pogledate gornji izraz, on tvori geometrijsku progresiju (a, ar, ar^2, ar^3 ...... beskonačno vrijeme). Zbroj GP je dan sa S(N) = a / (r - 1). Ovdje je prvi član i r je zajednički omjer.