rekursiiviseen

Rekursiivisuus on käsite, joka kuvaa ilmiötä, jossa ratkaisu tai määritelmä viittaa itseensä. Rekursiiviset mallit ja rakenteet rakentuvat siitä, että ongelma jaetaan pienempiin, samankaltaisiin osiin ja ratkaisut lasketaan käyttämällä samaa menetelmää useammassa vaiheessa. Yleisessä muodossa rekursio tarvitsee pohja- eli perusehdon sekä rekursiovaiheen, jossa ratkaisu rakennetaan aiemmin määritellyistä osista.

Matematiikassa ja muodollisessa määritelmässä rekursiivinen määritelmä koostuu pohjaehdosta ja rekursiovaiheesta. Esimerkki on n! määritelmä: 0! = 1 ja n! = n·(n−1)! (n > 0). Toinen tunnettu esimerkki on Fibonacci-lukujen n:nnen termi, joka määritellään edeltävien termien summana.

Tietojenkäsittelytieteessä rekursiiviset funktiot kutsuvat itseään, kunnes saavutetaan pohjaehdosta. Rekursio sopii ongelmiin, joissa ratkaisut voidaan rakentaa pienemmistä osista, esimerkiksi puiden ja graafien läpikäyntiin sekä monien algoritmien määrittelyyn. Plussaa on ilmeinen rakenne, miinuksena muistinkäyttö ja riski pinon ylittyä. Tyypillinen optimointi on tail recursion -optimointi tai rekursion muuttaminen silmukaksi.

Kielitieteessä rekursio tarkoittaa upotettujen lauseiden ja rakenteiden toistuvaa laajentamista. Rekursiivisuus mahdollistaa ilmauksen monimutkaisuuden rakentamisen itseään hyödyntäen.

Rekursiivisuus on keskeinen käsite matematiikassa, tietojenkäytössä ja kielitieteessä, ja sitä käytetään kuvaamaan ongelman tai määritelmän itseensä viittaavaa rakennetta.