Ste bili kdaj ujeti v navidezno neskončen cikel, v katerem se problem še naprej razveja na manjše fragmente?
Če je tako, ste morda naleteli na očarljiv svet rekurzije. Čeprav se zdi, da je težko razumeti, ne skrbite! V tej objavi se bomo podali na zanimivo potovanje, da bi spoznali vrste rekurzij.
Zato se pripnite, ko raziskujemo številne rekurzivne pristope. Pripravite se na vstop v fascinantno kraljestvo rekurzije in opazujte njeno izjemno sposobnost pri reševanju zapletenih vprašanj.
Kaj točno so rekurzije?
Z osnovnimi besedami je rekurzija zmogljiva tehnika programiranja, ki vključuje funkcijo, ki med izvajanjem kliče samo sebe. To je tako, kot če bi strmeli v ogledalo in videli sliko znotraj slike, kar ima za posledico samoreferenčni cikel.
Z rekurzijo se lahko lotimo velikih težav tako, da jih razdelimo na manjše, bolj obvladljive podprobleme.
Podobno je sestavljanju sestavljanke, kjer je en kos povezan z drugimi deli, da ustvari celotno sliko. Rekurzija nam omogoča reševanje težav na eleganten in učinkovit način s ponavljanjem istega niza navodil z različnimi vhodi.
1-neposredna rekurzija
Neposredna rekurzija je najosnovnejša vrsta rekurzije, pri kateri funkcija kliče neposredno samo sebe. Vključuje razdelitev problematičnega problema na manjše podprobleme, dokler ni dosežen osnovni primer, kar vodi v prekinitev.
Rekurzivna funkcija kliče samo sebe z različnimi vhodi, kar omogoča ponavljanje izvajanja istega niza navodil. Vsak priklic nadgrajuje prejšnjega in se postopoma približuje osnovnemu primeru, ki povzroči konec rekurzije.
Preverimo ta primer.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
izhod:
5
4
3
2
1
2-Posredna rekurzija
Posredna rekurzija dodaja zanimiv zasuk rekurzivni poti. V nasprotju z neposredno rekurzijo, ki vključuje eksplicitno klicanje funkcije, posredna rekurzija vključuje verigo klicev funkcij.
Ena funkcija pokliče drugo, ki lahko nato pokliče izvirno funkcijo ali katero koli drugo funkcijo, ki se končno vrne k izvirniku. Ta medsebojno povezana mreža funkcijskih klicev ustvarja očarljiv ples, v katerem več funkcij sodeluje pri odpravljanju težave.
primer:
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)
izhod:
A: 3
B: 2
A: 1
3-linearna rekurzija
Razmislite o potovanju po ravni poti, korak za korakom, dokler ne dosežete svojega cilja. To zaporedno tehniko uteleša linearna rekurzija, pri kateri funkcija izvede en sam rekurziven klic v vsaki ponovitvi funkcije.
Z vsakim rekurzivnim klicem se rekurzivni proces približa osnovnemu primeru z zmanjšanjem velikosti težave. Poteka na jasen in linearen način, rešuje podprobleme enega za drugim, dokler ni dosežen končni odgovor.
primer:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
izhod:
120
4-drevesna rekurzija
Ko se funkcija razveji na več rekurzivnih klicev, vstopimo v svet drevesne rekurzije. Funkcija v drevesni rekurziji ustvari številne rekurzivne klice, od katerih vsak rešuje ločen podproblem, tako kot to počnejo veje drevesa.
Ta razvejana struktura omogoča hkratno preiskavo več poti, pri čemer učinkovito razčleni zapletena vprašanja na manjše, medsebojno povezane komponente.
primer:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
izhod:
8
5-gnezdena rekurzija
Ugnezdena rekurzija doda vznemirljivo stopnjo kompleksnosti rekurzivnemu vesolju. V tej obliki rekurzije funkcija vključuje rekurzivni klic kot argument znotraj drugega rekurzivnega klica.
Notranji rekurzivni klic deluje na vrednost, ki je odvisna od zunanjega rekurzivnega klica. Kompleksnost raste z vsakim ugnezdenim klicem, kar doseže vrhunec v zanimivem vzorcu ugnezdenih rekurzivnih klicev.
primer:
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 optimizacijska tehnika za rekurzivne algoritme, ki lahko izboljša njihovo delovanje. Rekurzivni klic se pojavi kot končno dejanje funkcije z repno rekurzijo, ustvarjanje.
Ker po rekurzivnem klicu ni odprtih operacij, lahko prevajalnik ali tolmač poenostavi rekurzijo tako, da jo nadomesti s preprostim skokom.
Ta optimizacijski pristop, znan kot optimizacija repnega klica, zmanjša zahtevo za vsak rekurzivni klic, da ohrani okvir sklada, kar ima za posledico večjo hitrost in manjšo porabo pomnilnika.
primer:
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 brez repa
V nasprotju z repno rekurzijo rekurzija brez repa vključuje dodatne dejavnosti, ki se izvajajo po rekurzivnem klicu znotraj funkcije. Preden se lahko izvedejo nadaljnja dejanja, se mora vsak rekurzivni klic dokončati in vrniti.
Posledično, dokler ni dosežen osnovni primer in se rekurzija ne konča, se vzdržuje kup odprtih operacij. Rekurzija brez repa pogosto uporablja več pomnilnika in je manj učinkovita od rekurzije z repom, vendar je še vedno koristno orodje za reševanje različnih težav.
primer:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
izhod:
15
Zaviti
Rekurzija je zanimiv koncept v programiranju. Omogoča nam, da se zapletenih problemov lotimo na rekurziven, samoreferenčen način.
Ponuja posebno metodo razmišljanja in reševanja problemov, ki jih razdeli na manjše, bolj obvladljive dele. Vendar pa je pri delu z rekurzijo ključnega pomena, da bodite pozorni na nekatere točke.
Identificirati morate primerne osnovne primere, ki omogočajo zaključek rekurzije. Če niso prisotni, se lahko funkcija za vedno kliče sama.
Drugič, na podlagi obravnavanega scenarija lahko izbira ustrezne vrste rekurzije vodi do učinkovitejših in elegantnejših rešitev. Poskusite najti tisto, kar je najboljše za težavo v roki. Ko delate z velikimi globinami rekurzije, bodite pozorni na možne nevarnosti, kot je prelivanje sklada.
Pustite Odgovori