Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C++

Rekurzija

Rekurzija pomeni, da funkcija pokliče samo sebe, neposredno ali prek drugih funkcij. Da se izračun konča, potrebuje dosegljiv osnovni primer in rekurzivne korake, ki napredujejo proti temu primeru.

Različica: C++23; repository compiler flag, production runtime not attested

Sintaksa

ReturnType function(Parameters) {
    if (base_condition) return base_value;
    return combine(function(smaller_arguments));
}

Rekurzija (recursion) je tehnika, pri kateri funkcija pokliče samo sebe neposredno ali posredno prek drugih funkcij. Ne potrebuje posebne ključne besede: uporablja običajno sintakso klica funkcije. C++ dovoljuje rekurzivne klice, vendar se main ne sme klicati rekurzivno.

Tipičen algoritem ima osnovni primer, ki vrne rezultat brez nadaljnjega klica, in rekurzivni korak, ki zmanjša problem. Pri vhodnih podatkih, pri katerih naj bi se izračun končal, mora vsaka veriga klicev doseči osnovni primer. Samo pogoj za ustavitev ne zadostuje, če ga argumenti nikoli ne izpolnijo.

V primeru sum_to(5) izračuna vsoto od 1 do vključno 5. Klici zmanjšujejo n, dokler ne doseže 0; ob zaporednih vrnitvah se nato prištejejo čakajoče vrednosti, rezultat pa je 15. Vsak klic ima svoj parameter n; ne gre za eno skupno spremenljivko. Za n <= 0 funkcija vrne 0.

Primera ne obravnavaj kot rešitev za poljubno velike vhodne podatke: globoka rekurzija lahko izčrpa izvajalne vire, vsota zunaj območja tipa int pa povzroči nedefinirano vedenje. Pri velikih vhodnih podatkih razmisli o zanki in preverjanju območja. Navedeni vir je razvijajoči se osnutek standarda, ne nespremenjena izdaja C++23; primer uporablja sintakso, združljivo s C++23.

Primeri

#include <iostream>

int sum_to(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

int main() {
    std::cout << sum_to(5) << '\n';
}

Rezultat

15

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri