Jeste li ikada bili uhvaćeni u naizgled beskrajnom ciklusu u kojem se problem nastavlja granati na manje dijelove?
Ako je tako, možda ste naišli na očaravajući svijet rekurzije. Iako se može činiti da je teško razumjeti, ne brinite! U ovom ćemo postu krenuti na zanimljivo putovanje kako bismo naučili o vrstama rekurzija.
Zato se zakopčajte dok istražujemo brojne rekurzivne pristupe. Pripremite se za ulazak u fascinantno carstvo rekurzije i promatrajte njezinu izvanrednu sposobnost u rješavanju kompliciranih problema.
Što su zapravo rekurzije?
Osnovnim riječima, rekurzija je moćna tehnika programiranja koja uključuje pozivanje same sebe funkcije tijekom izvođenja. To je kao da zurite u ogledalo i vidite sliku unutar slike, što rezultira samoreferentnim ciklusom.
Velikim se problemima možemo pozabaviti pomoću rekurzije tako da ih podijelimo na manje podprobleme kojima se lakše može upravljati.
To je slično sastavljanju slagalice, gdje se jedan dio povezuje s drugim dijelovima kako bi se dobila cjelovita slika. Rekurzija nam omogućuje rješavanje problema na elegantan i učinkovit način ponavljanjem istog skupa uputa s različitim unosima.
1-izravna rekurzija
Izravna rekurzija je najosnovniji tip rekurzije, u kojem funkcija sama sebe poziva izravno. To podrazumijeva dijeljenje problematičnog problema na manje podprobleme dok se ne postigne osnovni slučaj, što dovodi do prekida.
Rekurzivna funkcija poziva samu sebe različitim unosima, omogućujući ponavljanje izvršenja istog skupa instrukcija. Svaki poziv nadograđuje se na prethodni, postupno se približava osnovnom slučaju koji uzrokuje završetak rekurzije.
Provjerimo ovaj primjer.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Izlaz:
5
4
3
2
1
2-Neizravna rekurzija
Neizravna rekurzija dodaje intrigantan zaokret rekurzivnom putu. Za razliku od izravne rekurzije, koja uključuje eksplicitno pozivanje funkcije same sebe, neizravna rekurzija uključuje lanac poziva funkcija.
Jedna funkcija poziva drugu, koja zatim može pozvati izvornu 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 surađuje kako bi riješile 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 utjelovljena je linearnom rekurzijom, u kojoj funkcija izvodi jedan rekurzivni poziv u svakoj iteraciji funkcije.
Sa svakim rekurzivnim pozivom, rekurzivni proces se približava osnovnom slučaju smanjujući veličinu problema. Nastavlja se na jasan i linearan način, rješavajući podprobleme jedan po jedan dok se ne dođe do konačnog odgovora.
Primjer:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Izlaz:
120
Rekurzija 4 stabla
Kada se funkcija grana u nekoliko rekurzivnih poziva, ulazimo u svijet rekurzije stabla. Funkcija u rekurziji stabla generira mnoge rekurzivne pozive, od kojih svaki rješava zasebni podproblem, baš kao što to rade grane stabla.
Ova struktura grananja omogućuje istovremeno istraživanje nekoliko ruta, učinkovito razlažući komplicirana 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 uzbudljivi stupanj složenosti rekurzivnom svemiru. U ovom obliku rekurzije, funkcija uključuje rekurzivni poziv kao argument unutar drugog rekurzivnog poziva.
Unutarnji rekurzivni poziv djeluje na vrijednost koja ovisi o vanjskom rekurzivnom pozivu. Složenost raste sa svakim ugniježđenim pozivom, kulminirajući intrigantnim uzorkom 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-repa rekurzija
Repna rekurzija je tehnika optimizacije za rekurzivne algoritme koja može poboljšati njihovu izvedbu. Rekurzivni poziv pojavljuje se kao završna radnja funkcije s repnom rekurzijom, stvaranjem.
Budući da nema neizvršenih operacija nakon rekurzivnog poziva, kompilator ili tumač može pojednostaviti rekurziju zamjenom s jednostavnim skokom.
Ovaj pristup optimizaciji, poznat kao optimizacija repnog poziva, smanjuje zahtjev da svaki rekurzivni poziv zadrži okvir stoga, što rezultira poboljšanom brzinom i manjom upotrebom 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 mogu izvršiti bilo kakve daljnje radnje, svaki rekurzivni poziv mora završiti i vratiti se.
Kao posljedica toga, sve dok se ne dosegne osnovni slučaj i dok rekurzija ne završi, održava se hrpa neizvršenih operacija. Rekurzija bez repa često koristi više memorije i manje je učinkovita od repne rekurzije, ali je još uvijek 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ćuje nam da se uhvatimo u koštac s kompliciranim problemima na rekurzivan, samoreferencijalan način.
Nudi posebnu metodu razmišljanja i rješavanja problema, razlažući ih na manje dijelove kojima se lakše upravlja. Međutim, kad radite s rekurzijom, ključno je obratiti pozornost na neke točke.
Trebali biste identificirati odgovarajuće osnovne slučajeve koji omogućuju završetak rekurzije. Ako nisu prisutni, funkcija može zauvijek nastaviti pozivati samu sebe.
Drugo, na temelju scenarija koji je pri ruci, odabir odgovarajuće vrste rekurzije može dovesti do učinkovitijih 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 stogova.
Ostavi odgovor