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.