rekursiossa

Rekursiossa (rekursio) ratkaistaan ongelma käyttämällä itse samaa menetelmää pienemmillä, samanlaisen ongelman alimmilla tasoilla. Ratkaisussa on perus- eli pohjaehto, jolla ratkaisu voidaan määritellä ilman rekursiota, sekä rekursiivinen vaihe, jossa suurempi ongelma jaetaan pienempään ja ratkaisu lasketaan kutsumalla samaa menetelmää uudelleen.

Esimerkkinä usein käytetään n:n kertomaa n!, jossa n! = n × (n−1)!, ja perusvaihe on 0! = 1. Toinen yleinen esimerkki on Fibonacci-luvut, joissa jokainen luku muodostuu kahden edeltäjän summasta ja ratkaisut etenevät askeleittain kohti pohjaehtoa. Rekursiota käytetään myös käsittelemään hierarkkisia rakenteita kuten puita ja grafiikkaa, joissa ratkaisut johdetaan alirakenteista ylöspäin.

Rekursio liittyy kiinteästi myös ohjelmointiin ja matematiikkaan. Ohjelmoinnissa rekursio tarjoaa suoran tavan mallintaa luokkia, puuita ja jaksoittaista toimintaa, mutta se voi voimistaa muistinkäyttöä pinoon johtuvien kutsujen vuoksi. Siksi on tärkeää huomioida lopetusehto ja mahdolliset optimoinnit, kuten tail recursion -optimointi, jossa rekursiokutsu on viimeinen operaatio funktiossa.

Erilaisia rekursiotapoja ovat myös toisiaan kutsuva rekursio ja mutual recursion, joissa useampi funktio kutsuu toisiaan peräkkäin. Rekursi on tehokas ja ilmeikäs tapa määritellä ratkaisuja, kun ongelma luonnehtii itseään pienemmillä, samanlaisilla muodoilla.