Recursiveominaisuus

Recursiveominaisuus, tai rekursiivisuus, on ominaisuus, jossa ilmiö voidaan määritellä tai ratkaista käyttämällä itseään. Rekursiivinen määritelmä sisältää yleisesti lähtötapauksen sekä rekursiivisen askeleen, jossa suurempi osa viitataan samaan ilmiöön pienemmässä mittakaavassa. Tällainen rakenne mahdollistaa monimutkaisten asioiden ilmaisun yksinkertaisesti.

Matematiikassa rekursiivisia määritelmiä käytetään laajalti. Esimerkkinä: naturaaliluvut sekä n! määritellään rekursiivisesti niin, että 0! = 1 ja n! = n · (n−1)!, kun n > 0. Rekursio voidaan nähdä tapana rakentaa perusasioista vähitellen kohti lopullista ratkaisua.

Tietojenkäsittelytieteessä rekursio tarkoittaa funktiota, joka kutsuu itseään ratkaistakseen ongelman. Tämä lähestymistapa voi yksinkertaistaa monimutkaisten tehtävien ohjelmointia, kuten laskemista tai hakutoimintoja. On tärkeää, että jokaisessa rekursiossa on selvä perus- tai lähtötilanne sekä mekanismi, joka vie tilannetta kohti sitä. Ilman asianmukaista päätepäivää rekursio voi johtaa ei-päättymiseen, aiheuttaen virheitä tai pinon ylivuodon; usein ratkaisuja toteutetaan iteratiivisilla tavoilla tai käytetään tail recursion -optimointia, jos kieli tukee sitä.

Rakenteissa rekursiivinen määritelmä kuvaa itseään sisältäviä rakenteita, kuten binaari- tai monitasuisia puita. Esimerkiksi puu määritellään usein joko tyhjänä puuna tai solmuna, jolla on vasen ja oikea alipu. Tällaiset määritelmät ja käsitteet ovat keskeisiä rekursion käyttötarkoituksissa ja teoreettisessa informaatiossa.