Inoiz harrapatu al zara amaigabea dirudien ziklo batean arazo bat zati txikiagoetan adarkatzen jarraitzen duen?
Hala bada, baliteke errekurtsioaren mundu liluragarriarekin topo egitea. Ulertzea zaila dirudien arren, ez kezkatu! Post honetan, bidaia interesgarri bat egingo dugu errekurtsio motak ezagutzeko.
Beraz, zintzilikatu ikuspegi errekurtsibo ugari aztertzen ditugun heinean. Presta zaitez errekurtsioaren eremu liluragarrira sartzeko eta behatu gai konplikatuak konpontzeko duen gaitasun nabarmena.
Zer dira zehazki errekurtsoak?
Oinarrizko hitzetan, errekurtsioa programazio-teknika indartsua da, exekuzioan bere buruari deitzen dion funtzio bat barne hartzen duena. Ispiluari begira egotea eta irudi baten barruan irudi bat ikustea bezalakoa da, autoerreferentziazko ziklo bat sortuz.
Errekurtsioa erabiliz arazo handiei aurre egin diezaiekegu azpiarazo txikiago eta kudeagarriagoetan banatuz.
Puzzle bat muntatzearen antzekoa da, non pieza bat beste zati batzuekin lotzen den irudi osoa sortzeko. Errekurtsioak gaiak modu dotore eta eraginkorrean konpontzeko aukera ematen digu argibide-multzo bera hainbat sarrerarekin errepikatuz.
1-Zuzenean Errekurtsioa
Errekurtsio zuzena errekurtsio mota oinarrizkoena da, zeinetan funtzio batek bere buruari zuzenean deitzen dion. Arazo problematiko bat azpiarazo txikiagoetan banatzea dakar oinarrizko kasu bat lortu arte, eta horrek amaierara eramaten du.
Funtzio errekurtsiboak bere buruari dei egiten dio hainbat sarrerarekin, instrukzio-multzo beraren exekuzioa errepikatu ahal izateko. Dei bakoitza aurrekoaren gainean eraikitzen da, errekurtsioa amaitzea eragiten duen oinarrizko kasura pixkanaka hurbilduz.
Ikus dezagun adibide hau.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Irteera:
5
4
3
2
1
2-Zeharkako Errekurtsioa
Zeharkako errekurtsioak bira interesgarri bat gehitzen dio bide errekurtsiboari. Errekurtsio zuzenaren aldean, funtzio batek bere burua esplizituki deitzen duenaren aldean, zeharkako errekurtsioak funtzio-deien kate bat barne hartzen du.
Funtzio batek beste bati deitzen dio, eta, ondoren, jatorrizko funtzioari edo azkenean jatorrizkora itzultzen den beste edozein funtziori deitu diezaioke. Funtzio-deien sare honek dantza erakargarri bat sortzen du eta bertan hainbat funtziok arazo bat konpontzeko elkarlanean aritzen dira.
Adibidea:
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)
Irteera:
A: 3
B: 2
A: 1
3-Errekurtsio lineala
Demagun ibilbide zuzen batetik, urratsez urrats, zure helburura iritsi arte. Teknika sekuentzial hau errekurtsio linealaren bidez gauzatzen da, zeinetan funtzio batek dei errekurtsibo bakarra egiten duen funtzioaren iterazio bakoitzean.
Dei errekurtsibo bakoitzarekin, prozesu errekurtsiboa oinarrizko kasu batera hurbiltzen da arazoaren tamaina murriztuz. Modu argi eta linealean egiten du aurrera, azpiarazoak banan-banan ebatziz azken erantzunera iritsi arte.
Adibidea:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Irteera:
120
4-Zuhaitz Errekurtsioa
Funtzio bat hainbat dei errekurtsibotan adarkatzen denean, zuhaitzen errekurtsioaren munduan sartzen gara. Zuhaitz errekurtsioan funtzio batek dei errekurtsibo asko sortzen ditu, eta horietako bakoitzak azpiproblema bereizi bat ebazten du, zuhaitz baten adarrek egiten duten bezala.
Adarkatze-egitura honek hainbat ibilbide aldi berean ikertzea ahalbidetzen du, arazo konplikatuak modu eraginkorrean zatituz osagai txikiago eta elkarrekin erlazionatuta.
Adibidea:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Irteera:
8
5-Habiatutako Errekurtsioa
Errekurtsio habiatuak konplexutasun maila zirraragarria gehitzen dio unibertso errekurtsiboari. Errekurtsio-modu honetan, funtzio batek dei errekurtsibo bat beste dei errekurtsibo baten barruan argumentu gisa sartzen du.
Barneko dei errekurtsiboak kanpoko dei errekurtsiboaren menpe dagoen balio baten gainean jarduten du. Konplexutasuna habiatzen den deialdi bakoitzean habiatzen da, dei errekurtsibo habiaratuen eredu interesgarri batean amaitzen dena.
Adibidea:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Emaitza:
91
6-Buztana Errekurtsioa
Tail errekurtsioa algoritmo errekurtsiboetarako optimizazio teknika bat da, haien errendimendua hobetu dezaketenak. Dei errekurtsiboa buztan errekurtsioa duen funtzio baten azken ekintza gisa agertzen da, eginez.
Dei errekurtsiboaren ondoren eragiketa nabarmenik ez dagoenez, konpilatzaileak edo interpretatzaileak errekurtsioa sinplifikatu dezake, salto sinple batekin ordezkatuz.
Optimizazio-ikuspegi honek, buztan-deien optimizazioa izenez ezagutzen dena, dei errekurtsibo bakoitzaren eskakizuna murrizten du pila-markoa mantentzeko, eta ondorioz, abiadura hobetu eta memoria-erabilera txikiagoa da.
Adibidea:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Irteera:
120
7-Buztana ez den errekurtsioa
Isats-errekurtsioaren aldean, buztan ez-errekurtsioak funtzio baten barruan dei errekurtsiboaren ondoren egiten diren jarduera gehigarriak dakartza. Ekintza gehiago egin aurretik, dei errekurtsibo bakoitza amaitu eta itzuli behar da.
Ondorioz, oinarrizko kasura iritsi arte eta errekurtsioa amaitu arte, eragiketa nabarmenen pila bat mantentzen da. Isatsa ez den errekurtsioak maiz memoria gehiago erabiltzen du eta buztanezko errekurtsioa baino eraginkorragoa da, baina oraindik ere tresna lagungarria da hainbat arazori aurre egiteko.
Adibidea:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
Irteera:
15
biltzeko sortu
Errekurtsioa kontzeptu intrigazkoa da programazioan. Arazo konplikatuak modu errekurtsiboan, autoerreferentzial batean, aurre egiteko aukera ematen digu.
Arazoak pentsatzeko eta konpontzeko metodo ezberdina eskaintzen du, zati txikiago eta kudeatuagoetan banatuz. Errekurtsioarekin lan egitean, ordea, funtsezkoa da puntu batzuetan arreta jartzea.
Errekurtsioa amaitzea ahalbidetzen duten oinarrizko kasu egokiak identifikatu behar dituzu. Ez badaude, funtzioak bere buruari betiko deitzen jarrai dezake.
Bigarrenik, esku artean dagoen eszenatokian oinarrituta, errekurtsio mota egokia hautatzeak irtenbide eraginkorragoak eta dotoreagoak ekar ditzake. Saiatu eskuan dagoen arazorako egokiena dena aurkitzen. Errekurtsio-sakonera handiekin lan egiten duzunean, kontuan izan balizko arriskuez, hala nola pila gainezkatzea.
Utzi erantzun bat