Oletko koskaan joutunut loputtomalta näyttävään kierteeseen, jossa ongelma haarautuu jatkuvasti pienempiin palasiksi?
Jos näin on, olet ehkä törmännyt rekursion kiehtovaan maailmaan. Vaikka sen ymmärtäminen saattaa tuntua haastavalta, älä huoli! Tässä viestissä lähdemme mielenkiintoiselle matkalle oppiaksemme rekursiotyypeistä.
Ota siis kiinni, kun tutkimme lukuisia rekursiivisia lähestymistapoja. Valmistaudu astumaan kiehtovaan rekursion maailmaan ja tarkkaile sen huomattavaa kykyä ratkaista monimutkaisia asioita.
Mitä rekursiot oikein ovat?
Perussanojen mukaan rekursio on tehokas ohjelmointitekniikka, joka sisältää toiminnon, joka kutsuu itseään suorituksen aikana. Se on kuin peiliin tuijottamista ja kuvan näkemistä kuvan sisällä, mikä johtaa itseviittaussykliin.
Voimme ratkaista suuria ongelmia käyttämällä rekursiota jakamalla ne pienempiin, paremmin hallittaviin aliongelmiin.
Se on samanlainen kuin palapelin kokoaminen, jossa yksi kappale linkitetään muihin osiin kokonaiskuvan tuottamiseksi. Rekursion avulla voimme ratkaista ongelmat tyylikkäästi ja tehokkaasti toistamalla samoja ohjeita eri syötteillä.
1-Suora rekursio
Suora rekursio on yksinkertaisin rekursiotyyppi, jossa funktio kutsuu itseään suoraan. Se merkitsee ongelmallisen ongelman jakamista pienempiin osaongelmiin, kunnes saavutetaan perustapaus, mikä johtaa lopettamiseen.
Rekursiivinen funktio kutsuu itseään useilla syötteillä, mikä mahdollistaa saman käskysarjan suorittamisen toistamisen. Jokainen kutsu perustuu edelliseen ja lähestyy vähitellen perustapausta, joka aiheuttaa rekursion päättymisen.
Tarkastetaan tämä esimerkki.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
lähtö:
5
4
3
2
1
2-Epäsuora rekursio
Epäsuora rekursio lisää kiehtovan käänteen rekursiiviseen polkuun. Toisin kuin suora rekursio, jossa funktio kutsuu eksplisiittisesti itseään, epäsuora rekursio sisältää funktiokutsujen ketjun.
Yksi funktio kutsuu toista, joka voi sitten kutsua alkuperäistä funktiota tai mitä tahansa muuta funktiota, joka lopulta palaa alkuperäiseen. Tämä toisiinsa yhdistetty funktiokutsujen verkko tuottaa kiehtovan tanssin, jossa useat toiminnot tekevät yhteistyötä korjatakseen ongelman.
Esimerkiksi:
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)
lähtö:
A: 3
B: 2
A: 1
3-lineaarinen rekursio
Harkitse matkaa suoraa reittiä pitkin askel kerrallaan, kunnes saavutat tavoitteesi. Tämä peräkkäinen tekniikka on toteutettu lineaarisella rekursiolla, jossa funktio suorittaa yhden rekursiivisen kutsun kussakin funktioiteraatiossa.
Jokaisella rekursiivisella kutsulla rekursiivinen prosessi siirtyy lähemmäksi perustapausta pienentämällä ongelman kokoa. Se etenee selkeästi ja lineaarisesti ja ratkaisee aliongelmat yksi kerrallaan, kunnes lopullinen vastaus on saavutettu.
Esimerkiksi:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
lähtö:
120
4-Tree Recursion
Kun funktio haarautuu useiksi rekursiivisiksi kutsuiksi, astumme puurekursion maailmaan. Funktio puun rekursiossa tuottaa useita rekursiivisia kutsuja, joista jokainen ratkaisee erillisen aliongelman, aivan kuten puun oksat tekevät.
Tämä haarautuva rakenne mahdollistaa useiden reittien samanaikaisen tutkimisen ja hajottaa tehokkaasti monimutkaiset asiat pienempiin, toisiinsa liittyviin osiin.
Esimerkiksi:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
lähtö:
8
5-Sisäkkäinen rekursio
Sisäkkäinen rekursio lisää jännittävän monimutkaisuuden asteen rekursiiviseen universumiin. Tässä rekursiomuodossa funktio sisältää rekursiivisen kutsun argumenttina toisessa rekursiivisessa kutsussa.
Sisäinen rekursiivinen kutsu vaikuttaa arvoon, joka on riippuvainen ulkoisesta rekursiivisesta kutsusta. Monimutkaisuus kasvaa jokaisen sisäkkäisen kutsun myötä, mikä huipentuu kiehtovaan sisäkkäisten rekursiivisten kutsujen malliin.
Esimerkiksi:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Tulos:
91
6-häntärekursio
Tail-rekursio on rekursiivisten algoritmien optimointitekniikka, joka voi parantaa niiden suorituskykyä. Rekursiivinen kutsu näkyy funktion viimeisenä toimintona, jossa on häntärekursio, tekeminen.
Koska rekursiivisen kutsun jälkeen ei ole jäljellä olevia operaatioita, kääntäjä tai tulkki voi yksinkertaistaa rekursiota korvaamalla sen yksinkertaisella hyppyllä.
Tämä optimointitapa, joka tunnetaan nimellä tail call -optimointi, vähentää jokaisen rekursiivisen puhelun vaatimusta säilyttää pinokehys, mikä lisää nopeutta ja vähentää muistin käyttöä.
Esimerkiksi:
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-Ei-häntärekursio
Toisin kuin häntärekursio, ei-häntärekursio sisältää ylimääräisiä toimintoja, jotka suoritetaan rekursiivisen kutsun jälkeen funktion sisällä. Ennen kuin muita toimintoja voidaan suorittaa, jokaisen rekursiivisen kutsun on suoritettava loppuun ja palattava.
Tämän seurauksena, kunnes perustapaus saavutetaan ja rekursio päättyy, pino jäljellä olevia operaatioita ylläpidetään. Ei-tail-rekursio käyttää usein enemmän muistia ja on vähemmän tehokas kuin häntärekursio, mutta se on silti hyödyllinen työkalu useiden ongelmien ratkaisemiseen.
Esimerkiksi:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
lähtö:
15
Paketoida
Rekursio on kiehtova käsite ohjelmoinnissa. Sen avulla voimme käsitellä monimutkaisia ongelmia rekursiivisesti, itseviittautumalla.
Se tarjoaa selkeän tavan ajatella ja ratkaista ongelmia ja jakaa ne pienempiin, paremmin hallittaviin paloihin. Rekursion kanssa työskennellessä on kuitenkin tärkeää kiinnittää huomiota joihinkin kohtiin.
Sinun tulee tunnistaa sopivat perustapaukset, jotka mahdollistavat rekursion päättymisen. Jos niitä ei ole, toiminto voi jatkaa kutsumistaan ikuisesti.
Toiseksi, kulloisenkin skenaarion perusteella oikeanlaisen rekursion valitseminen voi johtaa tehokkaampiin ja tyylikkäämpiin ratkaisuihin. Yritä löytää mikä toimii parhaiten kädessä olevaan ongelmaan. Kun työskentelet valtavien rekursioiden syvyyksien kanssa, ole tietoinen mahdollisista vaaroista, kuten pinon ylivuoto.
Jätä vastaus