Da li ste ikada bili uhvaćeni u naizgled beskonačan ciklus u kojem se problem nastavlja da se grana na manje fragmente?
Ako je tako, možda ste naišli na očaravajući svijet rekurzije. Iako vam se može činiti da je teško razumjeti, ne brinite! U ovom postu ćemo krenuti na zanimljivo putovanje kako bismo naučili o vrstama rekurzija.
Zato se vežite dok istražujemo brojne rekurzivne pristupe. Pripremite se da uđete u fascinantno carstvo rekurzije i uočite njenu izuzetnu sposobnost u rješavanju komplikovanih pitanja.
Šta su zapravo rekurzije?
U osnovi, rekurzija je moćna tehnika programiranja koja uključuje funkciju koja sama sebe poziva tokom izvršavanja. To je kao da gledate u ogledalo i vidite sliku unutar slike, što rezultira ciklusom samoreferenciranja.
Možemo se pozabaviti velikim problemima koristeći rekurziju tako što ćemo ih podijeliti na manje podprobleme kojima je lakše upravljati.
To je slično sastavljanju ubodne testere, gde se jedan deo povezuje sa drugim delovima da bi se dobila puna slika. Rekurzija nam omogućava da rješavamo probleme na elegantan i efikasan način ponavljanjem istog skupa instrukcija s različitim ulazima.
1-Direktna rekurzija
Direktna rekurzija je najosnovnija vrsta rekurzije, u kojoj funkcija direktno poziva samu sebe. To podrazumijeva podjelu problematičnog problema na manje podprobleme dok se ne postigne osnovni slučaj, što dovodi do prekida.
Rekurzivna funkcija poziva samu sebe s različitim ulazima, omogućavajući ponavljanje izvršenja istog skupa instrukcija. Svako pozivanje se nadovezuje na prethodni, progresivno se približava osnovnom slučaju što uzrokuje da se rekurzija završi.
Provjerimo ovaj primjer.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Izlaz:
5
4
3
2
1
2-Indirektna rekurzija
Indirektna rekurzija dodaje intrigantan zaokret rekurzivnoj putanji. Za razliku od direktne rekurzije, koja uključuje funkciju koja eksplicitno poziva samu sebe, indirektna rekurzija uključuje lanac poziva funkcija.
Jedna funkcija poziva drugu, koja onda može pozvati originalnu funkciju ili bilo koju drugu funkciju koja se konačno vraća na original. Ova međusobno povezana mreža poziva funkcija proizvodi očaravajući ples u kojem nekoliko funkcija sarađuje kako bi riješili problem.
Primjer:
def function_A(n):
if n > 0:
print("A:", n)
function_B(n - 1)
def function_B(n):
if n > 0:
print("B:", n)
function_A(n - 1)
function_A(3)
Izlaz:
A: 3
B: 2
A: 1
3-linearna rekurzija
Razmislite o putovanju ravnom rutom, korak po korak, dok ne stignete do cilja. Ova sekvencijalna tehnika je oličena linearnom rekurzijom, u kojoj funkcija obavlja jedan rekurzivni poziv u svakoj iteraciji funkcije.
Sa svakim rekurzivnim pozivom, rekurzivni proces se približava osnovnom slučaju smanjenjem veličine problema. Nastavlja se na jasan i linearan način, rješavajući podprobleme jedan po jedan dok se ne postigne konačni odgovor.
Primjer:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Izlaz:
120
4-rekurzija stabla
Kada se funkcija grana na nekoliko rekurzivnih poziva, ulazimo u svijet rekurzije stabla. Funkcija u rekurziji stabla generiše mnogo rekurzivnih poziva, od kojih svaki rješava poseban podproblem, baš kao što to rade grane stabla.
Ova struktura grananja omogućava istovremeno istraživanje nekoliko ruta, efektivno razbijajući komplikovana pitanja na manje, međusobno povezane komponente.
Primjer:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Izlaz:
8
5-ugniježđena rekurzija
Ugniježđena rekurzija dodaje uzbudljiv stepen složenosti rekurzivnom univerzumu. U ovom obliku rekurzije, funkcija uključuje rekurzivni poziv kao argument unutar drugog rekurzivnog poziva.
Unutrašnji rekurzivni poziv djeluje na vrijednost koja ovisi o vanjskom rekurzivnom pozivu. Složenost raste sa svakim ugniježđenim pozivanjem, što kulminira intrigantnim obrascem ugniježđenih rekurzivnih poziva.
Primjer:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Rezultat:
91
6-rekurzija
Rep rekurzija je tehnika optimizacije za rekurzivne algoritme koja može poboljšati njihove performanse. Rekurzivni poziv se pojavljuje kao konačna radnja funkcije sa rep rekurzijom, stvaranjem.
Pošto nema nerešenih operacija nakon rekurzivnog poziva, kompajler ili interpreter mogu pojednostaviti rekurziju tako što će je zamijeniti jednostavnim skokom.
Ovaj pristup optimizaciji, poznat kao optimizacija repnog poziva, smanjuje potrebu za svakim rekurzivnim pozivom da zadrži okvir steka, što rezultira povećanom brzinom i manjim korištenjem memorije.
Primjer:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Outout:
120
7-Rekurzija bez repa
Za razliku od repne rekurzije, rekurzija bez repa uključuje dodatne aktivnosti koje se izvode nakon rekurzivnog poziva unutar funkcije. Prije nego što se bilo koje dodatne radnje mogu izvršiti, svaki rekurzivni poziv mora biti završen i vratiti se.
Kao posljedica toga, sve dok se ne postigne osnovni slučaj i završi rekurzija, održava se hrpa izvanrednih operacija. Rekurzija bez repa često koristi više memorije i manje je efikasna od repne rekurzije, ali je i dalje koristan alat za rješavanje raznih problema.
Primjer:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
Izlaz:
15
Zamotati
Rekurzija je intrigantan koncept u programiranju. Omogućava nam da se pozabavimo komplikovanim problemima na rekurzivan, samoreferentan način.
Nudi poseban način razmišljanja i rješavanja problema, razbijajući ih na manje komade kojima je lakše upravljati. Međutim, kada radite sa rekurzijom, važno je obratiti pažnju na neke tačke.
Trebali biste identificirati odgovarajuće osnovne slučajeve koji omogućavaju da se rekurzija završi. Ako nisu prisutni, funkcija se može nastaviti pozivati zauvijek.
Drugo, na osnovu scenarija koji je pri ruci, odabir odgovarajuće vrste rekurzije može dovesti do efikasnijih i elegantnijih rješenja. Pokušajte pronaći ono što najbolje odgovara problemu u ruci. Kada radite s velikim dubinama rekurzije, budite svjesni potencijalnih opasnosti kao što je prelijevanje steka.
Ostavite odgovor