Rekursioita

Rekursio tarkoittaa ilmiötä, jossa ratkaisu määritellään itse itsensä kautta tai jolloin ratkaisu koostuu pienemmistä samanlaisten ongelmien ratkaisuista. Matematiikassa rekursio määrittelee ilmiön perus tapauksella (base case) ja rekursiivisella askeleella, jossa ratkaisu riippuu pienemmästä vastaavasta tapauksesta. Rekursiota voidaan käyttää suoran rekursion muodossa, jossa funktio kutsuu itseään, sekä toisiaan kutsuvana monirekursioina (mutual recursion).

Ohjelmoinnissa rekursio on yleinen tapa ratkaista ongelmia, jotka voidaan jakaa pienempiin osiin ja joissa samaa ratkaisua toistetaan. Keskeisiä käsitteitä ovat perus- eli lopetustapaus sekä rekursiivinen vaihe. Esimerkki: faktoriaali n! määritellään seuraavasti: n = 0 jolloin tulos on 1; muuten n! = n × (n−1)!. Toinen yleinen esimerkki on Fibonacci-sarja, jossa F(n) = F(n−1) + F(n−2) ja F(0) = 0, F(1) = 1.

Rekursio voi kuluttaa paljon muistia ja johtaa pinon ylivuotoon suurilla syötteillä. Jotkin kielet tukevat takaisirekursiota, jolloin rekursio voidaan optimoida käytännössä silmukaksi. Monirekursio voi olla selkeämpi mutta monimutkaisempi; memoointi eli tulosten tallennus voi nopeuttaa ratkaisuja, erityisesti Fibonacci-kaltaisissa tapauksissa.

Historia ja käyttöalueet: rekursio on keskeinen käsite sekä matematiikassa että tietojenkäytössä. Matematiikassa rekursio liittyy induktioon; ohjelmoinnissa rekursio mahdollisti puiden läpikäynnin, hajautusta ja tietyt dynaamisen ohjelmoinnin muotojen ratkaisut. Käytännössä rekursio on yleinen tekniikka algoritmeissa kuten puiden ja grafien käsittelyssä sekä divide-and-conquer-ratkaisuissa.