Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

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.

Zdroje