Erilaiset rekursiot

---

Rekursiiviset funktiot voidaan ominaisuuksiensa perusteella jakaa eri ryhmiin. Seuraavassa esitellään yleisiä rekursion muotoja.

• Suorassa rekursiossa funktio kutsuu itseään omassa rungossaan. Aiemman luvun kertoma-funktio on suoraan rekursiivinen.
• Epäsuorassa eli rinnakkaisrekursiossa funktio func_a kutsuu funktiota func_b, joka puolestaan kutsuu func_a-funktiota tai muuta funktiota kutsuketjussa. Kutsukehään voi osallistua useita funktioita.
• Häntärekursiossa rekursiivinen kutsu on funktion viimeinen suoritettava asia.

Häntärekursio

Funktio on häntärekursiivinen, jos rekursiivinen kutsu esiintyy kohdassa, jonka jälkeen funktiossa ei ole enää suoritettavia käskyjä eikä laskettavia lausekkeita. Kun kutsu palautuu, kutsuva funktio voi siis palauttaa saman tuloksen tekemättä enää mitään.

Aiempi kertoma-funktio ei ole häntärekursiivinen, koska rekursiivisen kutsun tulos täytyy vielä kertoa luvulla n:

return n * kertoma(n - 1);

Kertoman voi toteuttaa myös häntärekursiivisesti siirtämällä kertymässä olevan tuloksen ylimääräiseen parametriin:

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

Funktiota kutsutaan alkuarvolla 1, joka on kertoman perusehdon tulos 0! = 1:

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

Häntärekursion tulosta kootaan ylimääräiseen parametriin. Perusehdon täyttyessä kertynyt tulos palautetaan sellaisenaan. Siksi alkuarvon täytyy vastata triviaalitapauksen tulosta.

Häntärekursion muuntaminen silmukaksi

Häntärekursio voidaan muuttaa silmukaksi siirtämällä päivittyvät parametriarvot silmukan muuttujiin. Esimerkiksi kertoman voisi laskea näin:

unsigned int kertoma(unsigned int n) {
    unsigned int tulos = 1;
    while (n > 0) {
        tulos *= n;
        --n;
    }
    return tulos;
}

Silmukka välttää uuden funktiokutsun luomisen jokaisella kierroksella. Jotkin kääntäjät voivat optimoida häntärekursiivisia kutsuja, mutta C++ ei takaa tätä optimointia. Silmukaksi muuntaminen tekee muistinkäytöstä ennustettavaa.

Kokeile itse

Kokonaislukujen summaamisen voi toteuttaa häntärekursiivisesti. Lisää tehtävään funktio sum_tail_recursive, joka muuten vastaa aiempaa sum_recursive-funktiota mutta ottaa lisäksi yhden int-parametrin summan kertymistä varten. Päätä sopiva alkuarvo ja perusehto.