Vai esat kādreiz nonācis šķietami nebeidzamā ciklā, kurā problēma turpina sazaroties mazākos fragmentos?
Ja tā, iespējams, esat nonācis aizraujošajā rekursijas pasaulē. Lai gan šķiet, ka to ir grūti saprast, neuztraucieties! Šajā rakstā mēs dosimies interesantā ceļojumā, lai uzzinātu par rekursiju veidiem.
Tāpēc piesprādzējieties, pētot daudzas rekursīvas pieejas. Sagatavojieties ieiet aizraujošajā rekursijas valstībā un vērojiet tās ievērojamās spējas sarežģītu jautājumu risināšanā.
Kas īsti ir rekursijas?
Vārdu sakot, rekursija ir spēcīgs programmēšanas paņēmiens, kas ietver funkciju, kas izsauc sevi izpildes laikā. Tas ir tāpat kā skatīties spogulī un redzēt attēlu attēlā, kā rezultātā rodas pašreferences cikls.
Mēs varam risināt lielas problēmas, izmantojot rekursiju, sadalot tās mazākās, vieglāk pārvaldāmās apakšproblēmās.
Tas ir līdzīgi kā finierzāģa salikšana, kad viens gabals tiek savienots ar citām daļām, lai iegūtu pilnu attēlu. Rekursija ļauj mums eleganti un efektīvi atrisināt problēmas, atkārtojot vienu un to pašu instrukciju kopu ar dažādām ievadēm.
1 tiešā rekursija
Tiešā rekursija ir visvienkāršākais rekursijas veids, kurā funkcija izsauc sevi tieši. Tas ietver problemātiskas problēmas sadalīšanu mazākās apakšproblēmās, līdz tiek sasniegts bāzes gadījums, kas noved pie izbeigšanas.
Rekursīvā funkcija sevi izsauc ar dažādām ievadēm, ļaujot atkārtot vienas un tās pašas instrukciju kopas izpildi. Katra izsaukšana balstās uz iepriekšējo, pakāpeniski tuvojoties bāzes gadījumam, kas izraisa rekursijas beigas.
Pārbaudīsim šo piemēru.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Output:
5
4
3
2
1
2-Netiešā rekursija
Netiešā rekursija piešķir rekursīvajam ceļam intriģējošu pavērsienu. Atšķirībā no tiešās rekursijas, kas ietver funkciju, kas skaidri izsauc sevi, netiešā rekursija ietver funkciju izsaukumu ķēdi.
Viena funkcija izsauc citu, kas pēc tam var izsaukt sākotnējo funkciju vai jebkuru citu funkciju, kas beidzot atgriežas pie sākotnējās funkcijas. Šis savstarpēji savienotais funkciju izsaukumu tīkls rada aizraujošu deju, kurā vairākas funkcijas sadarbojas, lai atrisinātu problēmu.
Piemērs:
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)
Output:
A: 3
B: 2
A: 1
3-lineārā rekursija
Apsveriet braucienu pa taisnu maršrutu, soli pa vienam, līdz sasniedzat savu mērķi. Šo secīgo paņēmienu iemieso lineārā rekursija, kurā funkcija katrā funkcijas iterācijā veic vienu rekursīvu izsaukumu.
Ar katru rekursīvo zvanu rekursīvais process tuvojas bāzes gadījumam, samazinot problēmas lielumu. Tas notiek skaidri un lineāri, pa vienam risinot apakšproblēmas, līdz tiek sasniegta galīgā atbilde.
Piemērs:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Output:
120
4-Tree Recursion
Kad funkcija sazarojas vairākos rekursīvos izsaukumos, mēs nonākam koku rekursijas pasaulē. Funkcija koka rekursijā ģenerē daudzus rekursīvus izsaukumus, no kuriem katrs atrisina atsevišķu apakšproblēmu, tāpat kā koka zari.
Šī sazarotā struktūra ļauj vienlaikus izpētīt vairākus maršrutus, efektīvi sadalot sarežģītos jautājumus mazākos, savstarpēji saistītos komponentos.
Piemērs:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Output:
8
5 ligzdota rekursija
Ligzdota rekursija piešķir rekursīvajam Visumam aizraujošu sarežģītības pakāpi. Šajā rekursijas formā funkcija ietver rekursīvu izsaukumu kā argumentu citā rekursīvajā izsaukumā.
Iekšējais rekursīvais izsaukums iedarbojas uz vērtību, kas ir atkarīga no ārējā rekursīvā izsaukuma. Sarežģītība pieaug ar katru ligzdoto izsaukšanu, kas beidzas ar intriģējošu ligzdotu rekursīvu zvanu modeli.
Piemērs:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Rezultāts:
91
6 astes rekursija
Tail rekursija ir optimizācijas paņēmiens rekursīviem algoritmiem, kas var uzlabot to veiktspēju. Rekursīvais izsaukums parādās kā funkcijas beigu darbība ar astes rekursiju, padarīšanu.
Tā kā pēc rekursīvā izsaukuma nav nevienas izcilas darbības, kompilators vai tulks var vienkāršot rekursiju, aizstājot to ar vienkāršu lēcienu.
Šī optimizācijas pieeja, kas pazīstama kā gala izsaukuma optimizācija, samazina prasību katram rekursīvajam zvanam saglabāt steka rāmi, kā rezultātā palielinās ātrums un samazinās atmiņas lietojums.
Piemērs:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Ārpus:
120
7-Ne-astes rekursija
Atšķirībā no astes rekursijas, ne-astes rekursija ietver papildu darbības, kas tiek veiktas pēc rekursīvā izsaukuma funkcijas ietvaros. Lai varētu veikt citas darbības, katrs rekursīvais izsaukums ir jāpabeidz un jāatgriežas.
Tā rezultātā, līdz tiek sasniegts bāzes gadījums un beidzas rekursija, tiek saglabāta neizpildīto darbību kaudze. Rekursija bez astes bieži izmanto vairāk atmiņas un ir mazāk efektīva nekā astes rekursija, taču tā joprojām ir noderīgs rīks dažādu problēmu risināšanai.
Piemērs:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
Output:
15
Satīt
Rekursija ir intriģējošs jēdziens programmēšanā. Tas ļauj mums risināt sarežģītas problēmas rekursīvā, pašreferences veidā.
Tā piedāvā atšķirīgu metodi, kā domāt un risināt problēmas, sadalot tās mazākās, vieglāk pārvaldāmās daļās. Tomēr, strādājot ar rekursiju, ir ļoti svarīgi pievērst uzmanību dažiem punktiem.
Jums vajadzētu noteikt piemērotus bāzes gadījumus, kas ļauj beigt rekursiju. Ja to nav, funkcija var turpināt sevi izsaukt uz visiem laikiem.
Otrkārt, pamatojoties uz konkrēto scenāriju, atbilstoša rekursijas veida izvēle var radīt efektīvākus un elegantākus risinājumus. Mēģiniet atrast to, kas vislabāk atbilst rokas problēmai. Strādājot ar milzīgiem rekursijas dziļumiem, ņemiet vērā iespējamās briesmas, piemēram, skursteņa pārplūdi.
Atstāj atbildi