Kirjautuminen

Haku

Tehtävät

Oppaat: Ohjelmointiaiheita: Rekursio

Kirjoittaja: Antti Laaksonen. Vuosi: 2004.

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.

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:

Sekaisin olevat numerot jaetaan ryhmiin, jotka järjestellään, kun ne taas kootaan yhteen.

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@mbnet.fi. Ä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ä)

Kommentit

Turambar [12.09.2004 18:24:29]

Lainaa #

Eikös kertoma ole muuten määritetty vain luonnollisilla luvuilla, eikä kokonaisluvuilla?

Muutenkin selvennykseksi:
0! = 1! = 1
n! = 1*2*3...*n

Antti Laaksonen [12.09.2004 22:52:58]

Lainaa #

Hyvä huomautus, kertoman määrittely on tässä vähän vapaampi kuin matematiikassa yleensä. Funktiot kuitenkin toimivat oikein myös silloin, kun luku on 0.

jutti [12.02.2006 10:23:32]

Lainaa #

Tein kerran rekursiivisen ohjelman joka laski Fibonaccilukuja. Tämä on tyypillinen ongelma, jossa rekursiivisuus helposti jumittaa koneen. Eli:

int fibo(int n)
{
    if (n == 1) return 1;
    if (n == 2) return 1;
    if (n > 2) return fibo(n-1) + fibo(n-2);
}

Fibonacciluvut ovat 1, 1, 2, 3, 5, 8, 13, 21...

Rekursiivinen tekniikka on sinänsä mielenkiintoinen Fibonacciluvuissa, mutta iteratiivinen tekniikka toimii paremmin. Jos kokeilette tuota, lisätkää funktioon jokin näppäimistöä lukeva juttu, joka katkaisee funktion tarvittaessa. Muistaakseni fibo(20) oli jo ylivoimainen tehtävä, kesti jotain puoli tuntia.

Metabolix [14.07.2006 11:22:10]

Lainaa #

Mutta tuonpa takia kannattaakin taulukoida tuloksia, jottei samaa kohtaa tule laskettua useaan kertaan.

int fiboluvut[MAKSIMI] = {0};
int fibo(int n)
{
    if (n < 2) return 1;
    if (n >= MAKSIMI) return -1;
    if (fiboluvut[n] == 0) {
        fiboluvut[n] = fibo(n - 1) + fibo(n - 2);
    }
    return fiboluvut[n];
}

Loistava opas yhä edelleenkin. Esimerkkivalinnat ovat harvinaisen onnistuneita, niille tulee säännöllisesti käyttöä, kun vastailee toisten kysymyksiin.

moptim [07.07.2007 20:06:40]

Lainaa #

Heh. Fibonaccin lukujonon 20. alkio lähtisi todennäköisesti paperilla laskemalla alle puoleen tuntiin :D

pienipoika [06.08.2008 03:31:17]

Lainaa #

jutti kirjoitti:

Rekursiivinen tekniikka on sinänsä mielenkiintoinen Fibonacciluvuissa, mutta iteratiivinen tekniikka toimii paremmin. Jos kokeilette tuota, lisätkää funktioon jokin näppäimistöä lukeva juttu, joka katkaisee funktion tarvittaessa. Muistaakseni fibo(20) oli jo ylivoimainen tehtävä, kesti jotain puoli tuntia.

tuo pisti kyllä hiema silmään. tein tuon nimittäin tolla sun funktiolla ja tulos oli tämä:

pienipoika@Kompuutteri:~$ time ./testi 20
fibonaccin lukujonon 20. alkio = 6765

real    0m0.002s
user    0m0.000s
sys     0m0.000s

pienipoika@Kompuutteri:~$

Kirjoita kommentti

Huomio! Kommentoi tässä ainoastaan tämän oppaan hyviä ja huonoja puolia. Älä kirjoita muita kysymyksiä tähän. Jos koodisi ei toimi tai tarvitset muuten vain apua ohjelmoinnissa, lähetä viesti keskusteluun.

Muista lukea keskustelun ohjeet.
Tietoa sivustosta