Ar kada nors buvote įtrauktas į iš pažiūros nesibaigiantį ciklą, kai problema vis išsišakoja į mažesnius fragmentus?
Jei taip, galbūt patekote į žavingą rekursijos pasaulį. Nors tai gali atrodyti sudėtinga suprasti, nesijaudinkite! Šiame įraše leisimės į įdomią kelionę, kad sužinotume apie rekursijų tipus.
Taigi prisisekite, kai tyrinėjame daugybę rekursinių metodų. Pasiruoškite patekti į žavią rekursijos sritį ir stebėkite jos nepaprastus gebėjimus sprendžiant sudėtingas problemas.
Kas tiksliai yra rekursijos?
Paprastais žodžiais tariant, rekursija yra galinga programavimo technika, apimanti funkciją, kuri išsikviečia save vykdymo metu. Tai tarsi žvilgsnis į veidrodį ir atvaizdo viduje matymas, dėl kurio atsiranda savireferencijos ciklas.
Mes galime išspręsti dideles problemas naudodami rekursiją, suskirstydami jas į mažesnes, lengviau valdomas problemas.
Tai panašu į dėlionės sudarymą, kai vienas gabalas susiejamas su kitomis dalimis, kad būtų gautas visas vaizdas. Rekursija leidžia elegantiškai ir efektyviai išspręsti problemas kartojant tą patį instrukcijų rinkinį su įvairiomis įvestimis.
1-tiesioginė rekursija
Tiesioginė rekursija yra paprasčiausias rekursijos tipas, kai funkcija pati save vadina tiesiogiai. Tai reiškia, kad probleminė problema yra padalinta į smulkesnes dalis, kol pasiekiamas pagrindinis atvejis, o tai baigiasi.
Rekursyvinė funkcija iškviečia save įvairiais įėjimais, leidžiančiais kartoti tą patį komandų rinkinį. Kiekvienas iškvietimas grindžiamas ankstesniu, palaipsniui artėjant prie bazinio atvejo, dėl kurio baigiasi rekursija.
Patikrinkime šį pavyzdį.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Rezultatas:
5
4
3
2
1
2-Netiesioginė rekursija
Netiesioginė rekursija prideda intriguojančio rekursinio kelio posūkio. Priešingai nei tiesioginė rekursija, kuri apima funkciją, kuri aiškiai iškviečia save, netiesioginė rekursija apima funkcijų iškvietimų grandinę.
Viena funkcija iškviečia kitą, kuri gali iškviesti pradinę funkciją arba bet kurią kitą funkciją, kuri galiausiai grįžta į pradinę. Šis susietas funkcijų iškvietimų tinklas sukuria įspūdingą šokį, kuriame kelios funkcijos bendradarbiauja, kad išspręstų problemą.
Pavyzdys:
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)
Rezultatas:
A: 3
B: 2
A: 1
3-tiesinė rekursija
Apsvarstykite galimybę keliauti tiesiu maršrutu, po vieną žingsnį, kol pasieksite tikslą. Šią nuoseklią techniką įkūnija tiesinė rekursija, kai funkcija kiekvienoje funkcijos iteracijoje atlieka vieną rekursinį iškvietimą.
Su kiekvienu rekursiniu skambučiu rekursinis procesas priartėja prie bazinio atvejo sumažinant problemos dydį. Jis vyksta aiškiai ir linijiškai, sprendžiant subproblemas po vieną, kol gaunamas galutinis atsakymas.
Pavyzdys:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Rezultatas:
120
4-medžių rekursija
Kai funkcija išsišakoja į kelis rekursinius iškvietimus, patenkame į medžio rekursijos pasaulį. Medžio rekursijos funkcija generuoja daug rekursinių iškvietimų, kurių kiekvienas išsprendžia atskirą poproblemą, kaip tai daro medžio šakos.
Ši išsišakojusi struktūra leidžia vienu metu tirti kelis maršrutus, efektyviai suskaidant sudėtingas problemas į mažesnius tarpusavyje susijusius komponentus.
Pavyzdys:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Rezultatas:
8
5 įdėta rekursija
Įdėta rekursija rekursinei visatai suteikia jaudinančio sudėtingumo. Šioje rekursijos formoje funkcija įtraukia rekursinį skambutį kaip argumentą kitam rekursiniam skambučiui.
Vidinis rekursinis skambutis veikia pagal reikšmę, kuri priklauso nuo išorinio rekursinio skambučio. Sudėtingumas didėja su kiekvienu įdėtu iškvietimu ir baigiasi intriguojančiu įdėtų rekursinių skambučių modeliu.
Pavyzdys:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Rezultatas:
91
6 uodegos rekursija
Tail rekursija yra rekursinių algoritmų optimizavimo metodas, galintis pagerinti jų veikimą. Rekursyvus skambutis pasirodo kaip galutinis funkcijos veiksmas su uodegos rekursija, priėmimu.
Kadangi po rekursinio iškvietimo nėra jokių išskirtinių operacijų, kompiliatorius arba vertėjas gali supaprastinti rekursiją, pakeisdamas ją paprastu šuoliu.
Šis optimizavimo metodas, žinomas kaip uodegos skambučio optimizavimas, sumažina kiekvieno rekursinio skambučio reikalavimą išlaikyti krūvos kadrą, todėl padidėja greitis ir sumažėja atminties naudojimas.
Pavyzdys:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Išeina:
120
7-Ne uodegos rekursija
Priešingai nei uodegos rekursija, ne uodegos rekursija apima papildomą veiklą, atliekamą po rekursinio iškvietimo funkcijos viduje. Prieš atliekant bet kokius daugiau veiksmų, kiekvienas rekursinis skambutis turi būti baigtas ir grįžti.
Dėl to, kol nepasiekiamas pagrindinis atvejis ir baigiasi rekursija, išlaikoma neįvykdytų operacijų krūva. Ne uodegos rekursija dažnai naudoja daugiau atminties ir yra mažiau efektyvi nei uodegos rekursija, tačiau ji vis tiek yra naudinga priemonė sprendžiant įvairias problemas.
Pavyzdys:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
Rezultatas:
15
Apvynioti
Rekursija yra intriguojanti programavimo koncepcija. Tai leidžia mums spręsti sudėtingas problemas rekursyviai, referenciniu būdu.
Jis siūlo atskirą mąstymo apie problemas ir jų sprendimo metodą, suskaidant jas į mažesnes, lengviau valdomas dalis. Tačiau dirbant su rekursija, labai svarbu atkreipti dėmesį į kai kuriuos dalykus.
Turėtumėte nustatyti tinkamus bazinius atvejus, leidžiančius baigti rekursiją. Jei jų nėra, funkcija gali ir toliau vadintis save amžinai.
Antra, atsižvelgiant į esamą scenarijų, pasirinkus tinkamą rekursijos rūšį, galima rasti efektyvesnių ir elegantiškesnių sprendimų. Pabandykite rasti tai, kas geriausiai tinka rankoje esančiai problemai. Dirbdami su dideliais rekursijos gyliais, atkreipkite dėmesį į galimus pavojus, pvz., krūvos perpildymą.
Palikti atsakymą