Erilaiset rekursiot¶

Rekursiiviset funktiot voidaan ominaisuuksiensa perusteella jaotella ryhmiin, jotka kannattaa yleissivistyksen nimissä katsoa läpi.

Suoraksi rekursioksi kutsutaan tapausta, jossa funktio kutsuu itseään omassa rungossaan. Aikaisemman esimerkin kertoma on suoraan rekursiivinen.
Epäsuora rekursio eli rinnakkaisrekursio tarkoittaa tilannetta, jossa funktio func_a kutsuu funktiota func_b, joka taas kutsuu func_a:ta jne:

Sotkuun voi osallistua useampiakin funktioita, eli syntyvä “kutsukehä” voi olla pidempi.

Epäsuoran rekursion käytössä kannattaa olla pidättyväinen, koska se on usein hankalasti hahmotettava.
Häntärekursio, jota käsitellään seuraavaksi tarkemmin.

Häntärekursio¶

Funktio on häntärekursiivinen, jos rekursiivinen kutsu esiintyy funktiossa sellaisessa kohdassa, että kutsun jälkeen ei ole enää suoritettavia lauseita eikä evaluoitavia lausekkeita. Toisin sanoen rekursioiden “purkautuessa” kutsutussa funktiossa ei tehdä enää mitään.

Esimerkin kertoma-funktio ei ole häntärekursiivinen, koska rekursiivisen kutsun paluuarvo pitää ensin kertoa n:llä, jotta siitä saadaan paluuarvoksi kelpaava tulos:

return n * kertoma(n - 1);

Funktio kertoma voitaisiin toteuttaa häntärekursiivisena:

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

jota pitäisi kutsua siten, että jälkimmäiseksi parametriksi annetaan 1:

cout << kertoma(5, 1) << endl;

Tässä tapauksessa häntärekursiivisen funktion lopputulosta kerätään ylimääräiseen parametriin (tulos), johon kertynyt arvo voidaan palauttaa sellaisenaan lopetusehdon täyttyessä. Tästä seuraa, että ylimääräisen parametrin alkuarvon tulee olla triviaalitapauksen lopputulos. Miksi?

Häntärekursio on tärkeä käsite, koska se voidaan muuttaa mekaanisesti silmukkarakenteeksi. Näin saavutetaan rekursion hyödyt, mutta päästään eroon sen huonoista puolista.

Kokeile itse: Edellisessä tehtävässä toteutetun kokonaislukujen yhteenlaskun voi helposti toteuttaa myös häntärekursiivisena. Jos haluat kokeilla, lisää tiedostoon uusi funktio sum_tail_recursive, jonka määrittely on muuten täsmälleen sama kuin funktion sum_recursive, mutta sillä on vielä yksi ylimääräinen int-tyyppinen parametri, johon summaa aletaan laskea.