Rekursio

Rekursio yleisesti (V: 11 min)

Rekursiolla tarkoitetaan asian määrittelemistä itsensä avulla. Esimerkiksi luonnollisen luvun kertoma voidaan määritellä näin:

n! = n · (n − 1) · (n − 2) · … · 3 · 2 · 1, kun n > 0, ja lisäksi 0! = 1.

Nollaa suuremman luvun kertoma on siis luvun ja kaikkien sitä pienempien positiivisten kokonaislukujen tulo. Esimerkiksi 5! = 5 · 4 · 3 · 2 · 1 = 120.

Kertoman voi määritellä myös rekursiivisesti:

n! = 1, kun n = 0, ja n! = n · (n − 1)!, kun n > 0.

Esimerkiksi:

5! = 5 · 4!
   = 5 · 4 · 3!
   = 5 · 4 · 3 · 2!
   = 5 · 4 · 3 · 2 · 1!
   = 5 · 4 · 3 · 2 · 1 · 0!
   = 5 · 4 · 3 · 2 · 1 · 1
   = 120

Rekursiossa ongelma pyritään esittämään samanmuotoisina mutta yksinkertaisempina osaongelmina. Rekursiivista sääntöä sovelletaan osaongelmiin, kunnes saavutetaan niin yksinkertainen tapaus, jonka ratkaisu tiedetään suoraan.

Rekursion perusidea on jakaa ongelma pienempiin osiin ja ratkaista ne.

Rekursiiviset funktiot: kertoma

Ohjelmoinnissa rekursio liittyy usein funktioihin. Rekursiivinen funktio kutsuu itseään joko suoraan tai toisen funktion kautta.

Toteutetaan kertoman rekursiivinen määritelmä C++-funktiolla:

unsigned int kertoma(unsigned int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * kertoma(n - 1);
    }
}

Funktio laskee ja palauttaa parametrinsa n kertoman. Tarkastellaan vaihe vaiheelta kutsua kertoma(5):

Kertoma-funktion ensimmäinen aktivointi pääohjelmasta kutsuttaessa — Kertoma-funktiota on kutsuttu pääohjelmasta. Pääohjelman suoritus odottaa funktion palautumista.

Koska parametrin n arvo on 5, suoritetaan else-haara. Ennen kuin kertoma voi palauttaa arvon, sen täytyy laskea 5 * kertoma(4). Kutsun suoritus jää odottamaan rekursiivisen kutsun tulosta.

Kertoma-funktion aktivoinnit ensimmäisen rekursiivisen kutsun jälkeen — Ensimmäinen rekursiivinen kutsu on käynnissä parametrin arvolla 4.

Suoritus etenee samalla tavalla arvoilla 4, 3, 2 ja 1. Taustalle kertyy keskeneräisiä kertoma-funktion kutsuja.

Rekursio jatkuu, kunnes parametrin arvoksi tulee 0:

Kertoma-funktion aktivoinnit, kun parametrin arvo on nolla — Perusehto saavutetaan: parametrin `n` arvo on 0.

Nyt rekursiivista kutsua ei enää tehdä, vaan funktio palauttaa suoraan arvon 1. Keskeneräisten kutsujen pino alkaa purkautua. Syvimmästä kutsusta palataan kertomaan tulos parametrin arvolla 1:

Paluu syvimmästä rekursiivisesta kertoma-kutsusta — Paluu syvimmästä rekursiivisesta kutsusta.

Jokaisella keskeneräisellä funktiokutsulla on omat parametrien ja paikallisten muuttujien arvot. Kun rekursiivinen kutsu päättyy, kutsunut funktio jatkaa siitä, mihin sen suoritus pysähtyi.

Seuraavaksi jatkuu toiseksi syvin keskeneräinen kutsu, joka laskee 2 * 1:

Paluu toiseksi syvimmästä rekursiivisesta kertoma-kutsusta — Paluu toiseksi syvimmästä rekursiivisesta kutsusta.

Kutsut jatkavat purkautumistaan, kunnes ensimmäinen kertoma-kutsu on valmis:

Kertoma-funktion aktivoinnit juuri ennen paluuta pääohjelmaan — Kertoma-funktion viimeinen aktivointi juuri ennen paluuta pääohjelmaan.

Pääohjelma saa kutsun kertoma(5) tulokseksi 120.

Lisää esimerkkejä

Tämän kierroksen materiaaleissa on rekursiivinen toteutus lukusarjapelistä: examples/04/recursive_number_series_game/.

Esimerkkikoodissa on toinenkin rekursiivinen funktio, joka laskee kolmella ja seitsemällä jaollisten lukujen määrän annetulla välillä.

Yhteenveto

Rekursiiviset funktiot ovat tavallisia funktioita, jotka kutsuvat itseään. Rekursion hahmottaminen voi tuntua epäluontevalta, koska ratkaisu kuvataan pienempien samankaltaisten ongelmien avulla.

Rekursiivisten funktioiden suunnittelussa ja ymmärtämisessä kannattaa muistaa:

Funktio on rekursiivinen, jos se kutsuu itseään suoraan tai epäsuorasti.
Suorituksen aikana rekursiivisesta funktiosta on käynnissä yhtä monta kutsua kuin keskeneräisiä rekursiivisia kutsuja on.
Jokaisella kutsulla on omat parametrien ja paikallisten muuttujien arvot.

Jokaisella rekursiivisella funktiolla on oltava perusehto ja etenevä rekursiivinen tapaus.

Perusehto tunnistaa yksinkertaisen tapauksen ja ratkaisee sen ilman uutta rekursiivista kutsua.
Jokaisen rekursiivisen kutsun on yksinkertaistettava ongelmaa niin, että lopulta saavutetaan perusehto.

Kertomaesimerkissä perusehto on n == 0, jolloin vastaus tiedetään olevan 1. Jokaisessa rekursiivisessa kutsussa n pienenee yhdellä.

Jos perusehto puuttuu tai ongelma ei yksinkertaistu, seurauksena voi olla päättymätön rekursio. Keskeneräiset kutsut kuluttavat muistia, ja lopulta ohjelma voi kaatua esimerkiksi pinon ylivuotoon.

Rekursiolla voidaan toteuttaa toistoa, ja periaatteessa silmukan voi korvata rekursiolla. Rekursio sopii parhaiten ongelmiin, jotka luonnostaan jakautuvat pienempiin samanlaisiin osaongelmiin.

Rekursiivinen ratkaisu voi olla silmukkaratkaisua lyhyempi ja selkeämpi. Usein se kuitenkin kuluttaa enemmän aikaa ja muistia kuin vastaava silmukka.

Video: Merkkijonon suurin merkki (11 min)

Rekursiivisen funktion suunnittelu kannattaa aloittaa etsimällä perusehto: tilanne, jossa ongelma on helppo ratkaista suoraan.

Linkki videoon

Myös tietorakenteet voivat olla rekursiivisia. Rekursiivisten kutsujen lisäksi muistissa säilyy aiempiin kutsukierroksiin liittyvää tietoa.