Rekursio määritellään prosessiksi, joka kutsuu itseään suoraan tai epäsuorasti ja vastaavaa funktiota kutsutaan rekursiiviseksi funktioksi.
binäärihaun algoritmi
Rekursion ominaisuudet:
Rekursiolla on joitain tärkeitä ominaisuuksia. Jotkut niistä on mainittu alla:
- Rekursion ensisijainen ominaisuus on kyky ratkaista ongelma jakamalla se pienempiin osaongelmiin, joista jokainen voidaan ratkaista samalla tavalla.
- Rekursiivisella funktiolla on oltava perustapaus tai pysäytyskriteerit äärettömän rekursion välttämiseksi.
- Rekursioon kuuluu saman funktion kutsuminen itsessään, mikä johtaa kutsupinoon.
- Rekursiiviset funktiot voivat olla vähemmän tehokkaita kuin iteratiiviset ratkaisut muistin ja suorituskyvyn suhteen.
Rekursion tyypit:
- Suora rekursio: Kun funktiota kutsutaan itsessään suoraan, sitä kutsutaan suoraksi rekursioksi. Tämä voidaan edelleen luokitella neljään tyyppiin:
- Hännän rekursio,
- Pään rekursio,
- Puun rekursio ja
- Sisäkkäinen rekursio.
Lisätietoja rekursiotyypeistä on kohdassa Tämä artikkeli .
Rekursion sovellukset:
Rekursiota käytetään monilla tietojenkäsittelytieteen ja matematiikan aloilla, joihin kuuluvat:
pawandeep rajan
- Haku- ja lajittelualgoritmit: Rekursiivisia algoritmeja käytetään tietorakenteiden, kuten puiden ja kaavioiden, etsimiseen ja lajitteluun.
- Matemaattiset laskelmat: Rekursiivisia algoritmeja käytetään ratkaisemaan ongelmia, kuten tekijä, Fibonacci-sekvenssi jne.
- Kääntäjän suunnittelu: Rekursiota käytetään kääntäjien suunnittelussa ohjelmointikielien jäsentämiseen ja analysointiin.
- Grafiikka: monet tietokonegrafiikkaalgoritmit, kuten fraktaalit ja Mandelbrot-joukko, käyttävät rekursiota monimutkaisten kuvioiden luomiseen.
- Tekoäly: rekursiivisia hermoverkkoja käytetään luonnollisen kielen käsittelyssä, tietokonenäössä ja muissa tekoälysovelluksissa.
Rekursion edut:
- Rekursio voi yksinkertaistaa monimutkaisia ongelmia jakamalla ne pienempiin, paremmin hallittaviin osiin.
- Rekursiivinen koodi voi olla luettavampaa ja helpompi ymmärtää kuin iteratiivinen koodi.
- Rekursio on välttämätön joillekin algoritmeille ja tietorakenteille.
- Myös rekursiolla voimme lyhentää koodin pituutta ja tulla käyttäjälle/ohjelmoijalle luettavammaksi ja ymmärrettävämmäksi.
Rekursion haitat:
- Rekursio voi olla vähemmän tehokas kuin iteratiiviset ratkaisut muistin ja suorituskyvyn kannalta.
- Rekursiivisten funktioiden virheenkorjaus ja ymmärtäminen voi olla haastavampaa kuin iteratiiviset ratkaisut.
- Rekursio voi johtaa pinon ylivuotovirheisiin, jos rekursion syvyys on liian korkea.
Mitä muuta voit lukea?
- Rekursion tyypit
- Rekursiiviset funktiot