Rekursiivinen algoritmi

Rekursiivinen algoritmi on algoritmi, jonka toiminta perustuu rekursion käyttöön.

Rekursiivisia algoritmeja voidaan hyödyntää kirjoittamalla tietokoneohjelmia, joiden oleellinen ominaisuus on se, että ne voivat kutsua itseään. Rekursiivisen algoritmin oleelliset osat ovat:

• rekursiohaara ja
• päättymishaara.

Rekursiohaara kertoo, miten ongelma palautetaan yksinkertaisemman samaa tyyppiä olevan ongelman ratkaisemiseen. Päättymishaara ratkaisee kyseistä ongelmatyyppiä olevan triviaalin (yksinkertaisimman mahdollisen) ongelman, kun rekursiossa on edetty ko. tasolle. Esimerkiksi tehtävänä on laskea luvun 4 kertomafunktion arvo 4!=1x2x3x4.

• Tätä varten on laskettava ensin luvun 3 kertoma ja tämän jälkeen kerrottava se luvulla 4.
• Luvun 3 kertoman laskemiseksi on laskettava ensin luvun 2 kertoma ja tämän jälkeen kerrottava se luvulla 3.
• Luvun 2 kertoman laskemiseksi on laskettava ensin luvun 1 kertoma ja tämän jälkeen kerrottava se luvulla 2.
• Luvun 1 kertoma on triviaali ongelma, sillä tiedetään, että 1! = 1.

Palataan nyt rekursiossa taaksepäin.

• Luvun 2 kertoma on 2! = 2 x 1! = 2 x 1 = 2.
• Luvun 3 kertoma on 3! = 3 x 2! = 3 x 2 = 6.
• Luvun 4 kertoma on 4! = 4 x 3! = 4 x 6 = 24.

Edellä olevassa esimerkissä ei tapahdu haarautumista, koska ongelma palautuu aina yhden vastaavaa tyyppiä olevan, mutta yksinkertaisemman ongelman ratkaisemiseen. Yleensä haarautumista kuitenkin tapahtuu, ja tällöin on vaarana se, että se johtaa algoritmin suoritusajan ns. eksponentiaaliseen räjähdykseen.

Rekursiivisten algoritmien etuna on kuitenkin se, että rekursiota hyödyntäviä ohjelmia on helppo kirjoittaa ja ne ovat sopivaa ohjelmointikieltä käytettäessä lyhyitä ja elegantteja. Rekursiota tuntemattomalle ohjelmoijalle ne eivät kuitenkaan avaudu helposti.

Rekursiiviset aliohjelmat vaativat pinon käsittelyä, joka voi hidastaa ohjelmaa verrattuna toistorakenteen käyttöön. Eräissä kääntäjissä on tuki rekursion muuttamiseksi hyppykäskyiksi, joka poistaa funktiokutsun tuottaman lisäkuorman, jolloin käsittely on sama kuin toistorakennetta käyttämällä rekursion sijaan.

Rekursiivisia algoritmeja käytetään tyypillisesti tekoälyn tuottamiseen shakin tai vaikkapa tammen tyyppisiä lautapelejä tietokoneelle ohjelmoitaessa.

Eräs ongelma rekursiivisten algoritmien implementoinnissa on se, että ne jäävät helposti ikuiseen silmukkaan, mikäli päättymishaaraan ei syystä tai toisesta päädytäkään. Rekursiiviset algoritmit pitäisikin yleensä todistaa matemaattisesti oikeiksi ennen kuin implementointiin ryhdytään. Rekursiivisen algoritmin matemaattinen todistaminen voidaan suorittaa liittämällä tarkasteltavan ongelmatyypin jokaiseen yksittäiseen ongelmaan jokin luonnollinen luku siten, että triviaalia ongelmaa vastaa luku 0 tai 1. Tätä lukua sanomme ongelmatyypin kompleksisuusmitaksi. Tämän jälkeen osoitetaan että rekursiohaarassa kompleksisuusmitta pienenee, kunnes päädytään triviaaliin ongelmaan. Kertoman laskemisessa kompleksisuusmittana voitaisiin käyttää tarkasteltavaa lukua itseään.

Eräs ongelma on ns. piilorekursio. Tällä tarkoitetaan sitä, että mikään tarkasteltava ohjelma (aliohjelma) ei varsinaisesti kutsu itseään. Voi kuitenkin olla niin, että aliohjelma A kutsuu aliohjelmaa B, aliohjelma B aliohjelmaa C ja vaikkapa aliohjelma C jälleen aliohjelmaa A. Vaarana on jälleen joutuminen ikuiseen silmukkaan. Ohjelmien piilorekursiiviset ongelmat ovat usein vaikeasti selvitettävissä. Piilorekursiivisuutta on lähdekoodista vaikea havaita. Tämän takia piilorekursiivisiä algoritmeja tulisi välttää ohjelmoinnissa, koska ohjelmistoja joudutaan varsin usein ylläpitämään pitkiäkin aikoja, jolloin koodin helppolukuisuus parantaa ohjelmistojen ylläpidettävyyttä.

Aiheesta muualla

• Mastering recursive programming - IBM DeveloperWorks artikkeli aiheesta