rekursiivisen

Rekursiivinen on adjektiivi, jolla tarkoitetaan sitä, että jokin asia määritellään tai toteutetaan käyttämällä itseään viitteenä. Termi esiintyy sekä matematiikassa että tietojenkäsittelytieteessä sekä kielitieteessä, ja siihen liittyy ilmiö rekursio.

Matematiikassa rekursiivinen määritelmä määrittelee olion tai joukon käyttäen sitä itseään sekä perus- tai pohjapisteitä. Esimerkkejä ovat n:n kertomafunktio (n!) määritelmä: 0! = 1 ja n! = n·(n−1)!, sekä fibonaccin luvut F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2).

Tietojenkäsittelytieteessä rekursiiviset algoritmit ratkaisevat ongelmia kutsumalla itseään pienemmillä syötteillä, kunnes saavutetaan perusehto (base case). Tyypillisiä esimerkkejä ovat puu- ja grafitietojen läpikäynti sekä rekursiivinen tiedostojen ja hakemistojen käsittely. Monissa ohjelmointikielissä voidaan toteuttaa sekä yksittäistä rekursiota että toisiaan kutsuvia rekursiivisia funktioita (monirekursio).

Kielitieteessä rekursio kuvaa kykyä rakentaa lauseita sisäkkäisillä lausekkeilla ja säännöillä; monimutkaiset lauseet voivat sisältää toisen lauseen sisällä toisen kielellisen rakenteen. Rekursiivisuus on keskeinen käsite kielikielissä, joissa säännöt ovat itseään toistavia.

Rajoituksia ja toteutustekniikoita: rekursio on ilmaisultaan selkeä mutta voi johtaa suureen pinon käyttöön tai suorituksen hidastumiseen, jos syötteet ovat suuria. Monissa tapauksissa voidaan käyttää iteratiivista lähestymistapaa tai kääntäjän optimoimaa tail-recursionia.