Oppaat: Ohjelmointiaiheita: Rekursio

Rekursion toiminta perustuu siihen, että aliohjelma tai funktio kutsuu itseään uudestaan tiettyjen ehtojen perusteella. Näin on mahdollista toteuttaa monimutkaisia asioita vähällä määrällä koodia. Latinan kielen sana recurrere, joka tarkoittaa palaamista, kuvaa myös hyvin rekursion ajatusta, sillä ohjelman suoritus palaa aina lopulta uuden kierroksen aloittaneisiin risteyskohtiin. Rekursiivinen aliohjelma tai funktio joko kutsuu itseään uudestaan tai päättyy kutsumatta itseään, jos tietty ehto on täyttynyt. Lopetusehto on tärkeä, koska muuten ohjelma yleensä jumiutuu.

Tässä oppaassa on esitelty rekursion käyttötapoja esimerkkien avulla. Oppaassa olevat ohjelmat on kuvattu yksinkertaistettuina suomenkielisinä versioina, mutta tein ohjelmista myös C-, PHP- ja Visual Basic -kieliset versiot, jotka voit ladata tästä: rekursio.zip (5 kt). Paketissa on myös Lauri Kentän esimerkit Pascalille.

Ensimmäinen rekursio

Kokonaisluvun kertoma, joka merkitään n!, on luku kerrottuna sitä pienemmillä positiivisilla kokonaisluvuilla. Esimerkiksi 4! on 4 * 3 * 2 * 1 eli 24.

Tavallinen tapa laskea luvun kertoma on käyttää seuraavanlaista funktiota, jossa tulos kerrotaan kullakin kertoman muodostavalla luvulla:

funktio kertoma(luku)
    tulos = 1
    käy i väliltä 2 ja luku
        tulos = tulos * i
    palauta tulos

Kertoman voi laskea myös rekursiivisen funktion avulla. Silloin funktio näyttää seuraavalta:

funktio kertoma(luku)
    jos luku > 1
        palauta kertoma(luku - 1) * luku
    muuten
        palauta 1

Jos luku on suurempi kuin yksi, palautusarvona on luku itse kerrottuna yhtä pienemmän luvun kertomalla. Jos luku on yksi, palautusarvo on myös yksi. Nyt kun funktiolla lasketaan vaikkapa luvun neljä kertoma, se tapahtuu seuraavissa vaiheissa:

1. Palautetaan 3! * 4, pitää vielä laskea 3!.
2. Palautetaan 2! * 3, pitää vielä laskea 2!.
3. Palautetaan 1! * 2, pitää vielä laskea 1!.
4. Palautetaan 1, koska ehdossa on määrätty niin.
5. Nyt voidaan palauttaa 1! * 2, joka on 2.
6. Nyt voidaan palauttaa 2! * 3, joka on 6.
7. Nyt voidaan palauttaa 3! * 4, joka on 24.

Yhteensä kertoma-funktiota kutsutaan siis neljä kertaa sisäkkäin, ja funktioiden peräkkäinen kutsujono alkaa purkautua, kun päästään alimpaan lukuun eli yhteen.

Kumpi funktioista on sitten parempi kertoman laskemiseen? Rekursiivisen funktion toiminnan ymmärtäminen on vaikeampaa – ja se on myös alkuperäistä toteutusta hitaampi. Tämä todistaa sen, että rekursiota ei kannata yleensä käyttää, jos saman asian voi helposti toteuttaa ilmankin. Sisäkkäiset aliohjelmien ja funktioiden kutsut ovat hitaita ja kuluttavat muistia. Mutta seuraavaksi tulee joukko tilanteita, joihin rekursio sopii hyvin...

Hakemistojen läpikäynti

Monissa ohjelmointikielissä hakemistossa olevia tiedostoja ja alihakemistoja on mahdollista käydä läpi funktiolla, joka palauttaa joka kutsukerralla yhden tiedoston tai alihakemiston nimen kerrallaan. Rekursiivisen aliohjelman avulla koko hakemistorakenteen selaaminen on helppoa. Ohjelman rakenne on:

aliohjelma selaa(hakemisto, taso)
    nimi = luehakemisto(hakemisto)
    toista kunnes nimi on tyhjä
        tulosta 2 * taso väliä ja nimi
        selaa(hakemisto + nimi, taso + 1)
        nimi = luehakemisto()

Aliohjelma selaa käy läpi kaikki parametrina annetun hakemiston alihakemistot. Joka alihakemiston kohdalla aliohjelmaa kutsutaan uudestaan parametrina senhetkinen alihakemisto. Näin käydään läpi kaikki hakemistossa olevat alihakemistot. Toinen parametri taso ilmoittaa, millä hakemistotasolla kulloinkin ollaan. Tämän ansiosta kunkin hakemiston nimen eteen pystytään tulostamaan oikea määrä välilyöntejä, jotta hakemistojen puurakenne tulee esille. Ohjelman tulostus voisi olla seuraava:

omat
  ohjelmat
    c
    qb
  tekstit
pelit
  stunts
  triplane

Tästä selviää sekä aliohjelmien kutsujärjestys että hakemistopuun rakenne.

Yhdistelmien muodostaminen

Nyt tehtävänä on muodostaa kaikki yhdistelmät, joihin tietty määrä numeroita on mahdollista järjestää. Esimerkiksi numeroista 1, 2 ja 3 on mahdollista muodostaa kuusi erilaista yhdistelmää: 123, 132, 213, 231, 312 ja 321. Yhdistelmien määrä kasvaa nopeasti, kun numeroita tulee enemmän.

Tässä on rekursiivinen aliohjelma yhdistelmien muodostamiseen:

aliohjelma yhdistelmät(taso, määrä, sarja)
    jos taso = määrä
        tulosta sarja
    muuten
        käy i väliltä 1 ja määrä
            jos sarja ei sisällä i:tä
                lisää sarjaan i
                yhdistelmät taso + 1, määrä, sarja
                poista sarjasta i

Ensimmäinen parametri taso kertoo, kuinka mones numero on sillä hetkellä vuorossa. Numerosarjan pituuden ilmoittaa määrä-parametri, joka pysyy aina samana. Rakenteilla oleva numerosarja on sarja-parametrina. Jos taso ja määrä ovat samat, koko numerosarja on koossa ja sen voi näyttää. Muussa tapauksessa käydään läpi kaikki mahdollisesti sarjaan sopivat numerot. Jos numeroa ei ole valmiiksi sarjassa, se lisätään siihen ja siirrytään seuraavalla tasolle kutsumalla aliohjelmaa uusilla parametreilla.

Esimerkiksi kolminumeroiset yhdistelmät muodostetaan kutsumalla aliohjelmaa tasona 0, määränä 3 ja sarjana toteutustavasta riippuen tyhjä merkkijono tai lista. Seuraava listarakenne kuvaa hyvin aliohjelmien kutsujärjestystä. Vasemmalla olevat numerot ovat tasolla 1, keskellä olevat tasolla 2 ja oikealla olevat tasolla 3. Numero kerrallaan muodostettu yhdistelmä tulostetaan viimeisellä tasolla.

• 1

  • 2

    • 3

  • 3

    • 2

• 2

  • 1

    • 3

  • 3

    • 1

• 3

  • 1

    • 2

  • 2

    • 1

Samanlainen tekniikka sopii esimerkiksi kaikkien tietyistä kursseista muodostuvien lukujärjestysvaihtoehtojen selvittämiseen tai erimuotoisten palikoiden sovittamiseen pieneen ruudukkoon. Jos järjestettävä aineisto on laaja, sitä ei kuitenkaan välttämättä kannata kuljettaa aliohjelman parametrina, vaan parempi tapa on käyttää globaalia muuttujaa tai taulukkoa.

Taulukon lajitteleminen

Useat taulukon lajitteluun tarkoitetut algoritmit käyttävät hyväkseen rekursiota. Eräs tällainen lajittelualgoritmi on lomituslajittelu eli englanniksi mergesort, jonka toteutus näyttää yksinkertaistettuna seuraavalta:

funktio lajittelu(taulukko)
    jos taulukon koko > 1
        vasen = lajittelu(taulukon vasen puolisko)
        oikea = lajittelu(taulukon oikea puolisko)
        uusi = vasen ja oikea yhdistettynä järjestyksessä
        palauta uusi
    muuten
        palauta taulukko

Funktion sisällä taulukko jaetaan kahteen osaan, jotka kummatkin lajitellaan erikseen. Tämän jälkeen lajitellut pienemmät taulukot yhdistetään yhdeksi isoksi valitsemalla alkiot taulukoista suuruusjärjestyksessä. Jos taulukossa on kuitenkin vain yksi alkio, se palautetaan muuttumattomana. Seuraava kuva selventää lomituslajittelun toimintaa:

Lomituslajittelu on yksi tehokkaimmista lajittelutavoista, ja samalla sen toiminnan pystyy ymmärtämään helposti.

Lopuksi

Kun rekursion toiminnan ymmärtää, sitä oppii myös käyttämään oikeissa tilanteissa. Eräs hyvä harjoitusohjelma on laskulausekkeen ratkaiseminen (esim. (2 + 3) * 5 = 25). Rekursiota tarvitaan sulkujen käsittelyssä: sisimpänä olevat sulut lasketaan ensin, ja sitten mennään järjestyksessä sulkukerroksia alaspäin, kunnes vastaus on selvillä. Rekursion käytön lisäksi ohjelmaa tehdessä oppii paljon muutakin muun muassa merkkijonojen käsittelystä.

Jos sinulla on oppaaseen liittyvä kysymys tai haluat muuten vain antaa palautetta, lähetä sähköpostia osoitteeseen antti.laaksonen@ohjelmointiputka.net. Älä unohda kertoa viestissä, mistä aiheista haluaisit lukea jatkossa oppaita. Jos aihe sattuu olemaan minulle tuttu ja kiinnostava, opas voi hyvinkin ilmestyä jonakin päivänä.

Antti Laaksonen, 11.9.2004 (Pascal-esimerkit: Lauri Kenttä)