Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C++

Rekurze

Rekurze znamená, že funkce volá sama sebe, přímo nebo prostřednictvím jiných funkcí. Aby výpočet skončil, potřebuje dosažitelný základní případ a rekurzivní kroky, které k němu postupují.

Verze: C++23; repository compiler flag, production runtime not attested

Syntaxe

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

Rekurze (recursion) je technika, při které funkce volá sama sebe přímo nebo nepřímo prostřednictvím jiných funkcí. Nepotřebuje žádné zvláštní klíčové slovo: používá běžnou syntaxi volání funkce. C++ rekurzivní volání umožňuje, ale main se rekurzivně volat nesmí.

Typický algoritmus má základní případ, který vrátí výsledek bez dalšího volání, a rekurzivní krok, který zmenšuje problém. U vstupů, jejichž výpočet má skončit, musí každá posloupnost volání dosáhnout základního případu. Samotná podmínka ukončení nestačí, pokud její hodnoty argumentů nikdy nesplní.

V příkladu vypočítá sum_to(5) součet od 1 do 5 včetně. Volání snižují n, dokud nedosáhne 0; při postupném návratu se pak přičítají čekající hodnoty, takže výsledkem je 15. Každé volání má vlastní parametr n; nejde o jednu sdílenou proměnnou. Pro n <= 0 funkce vrátí 0.

Nepovažuj příklad za řešení pro libovolně velké vstupy: hluboká rekurze může vyčerpat prostředky pro běh programu a součet mimo rozsah typu int způsobuje nedefinované chování. U velkých vstupů zvaž cyklus a kontroly rozsahu. Uvedený zdroj je průběžně vyvíjený návrh standardu, nikoli neměnné vydání C++23; příklad používá syntaxi kompatibilní s C++23.

Příklady

#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';
}

Výsledek

15

Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje