CKTIS / C++
Rekurzia
Rekurzia znamená, že funkcia volá samu seba, priamo alebo prostredníctvom iných funkcií. Aby sa výpočet skončil, potrebuje dosiahnuteľný základný prípad a rekurzívne kroky, ktoré k nemu smerujú.
Verzia: C++23; repository compiler flag, production runtime not attested
Syntax
ReturnType function(Parameters) {
if (base_condition) return base_value;
return combine(function(smaller_arguments));
}Rekurzia (recursion) je technika, pri ktorej funkcia volá samu seba priamo alebo nepriamo prostredníctvom iných funkcií. Nepotrebuje žiadne špeciálne kľúčové slovo: používa bežnú syntax volania funkcie. C++ umožňuje rekurzívne volania, ale main sa nesmie volať rekurzívne.
Typický algoritmus má základný prípad, ktorý vráti výsledok bez ďalšieho volania, a rekurzívny krok, ktorý zmenšuje problém. Pri vstupoch, pri ktorých sa má výpočet skončiť, musí každá postupnosť volaní dosiahnuť základný prípad. Samotná podmienka zastavenia nestačí, ak jej argumenty nikdy nevyhovujú.
V príklade vypočíta sum_to(5) súčet od 1 po 5 vrátane. Volania znižujú n, kým nedosiahne 0; pri postupnom návrate sa potom sčítajú čakajúce hodnoty, čím vznikne 15. Každé volanie má vlastný parameter n; nejde o jednu spoločnú premennú. Pre n <= 0 funkcia vráti 0.
Nepovažuj príklad za riešenie pre ľubovoľne veľké vstupy: hlboká rekurzia môže vyčerpať zdroje vykonávania a súčet mimo rozsahu typu int spôsobuje nedefinované správanie. Pri veľkých vstupoch zváž cyklus a kontroly rozsahu. Uvedený zdroj je priebežne sa vyvíjajúci návrh štandardu, nie nemenné vydanie C++23; príklad používa syntax kompatibilnú s C++23.
Prí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ýsledok
15
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.