CKTIS / C++
Recursie
Bij recursie roept een functie zichzelf aan, rechtstreeks of via andere functies. Om de berekening te laten eindigen, is een bereikbaar basisgeval nodig en moeten de recursieve stappen daarnaartoe werken.
Versie: C++23; repository compiler flag, production runtime not attested
Syntax
ReturnType function(Parameters) {
if (base_condition) return base_value;
return combine(function(smaller_arguments));
}Recursie (recursion) is een techniek waarbij een functie zichzelf rechtstreeks of indirect via andere functies aanroept. Daarvoor is geen speciaal sleutelwoord nodig: recursie gebruikt de gewone syntaxis voor functieaanroepen. C++ staat recursieve aanroepen toe, maar main mag niet recursief worden aangeroepen.
Een typisch algoritme heeft een basisgeval, dat een resultaat teruggeeft zonder nog een aanroep te doen, en een recursieve stap, die het probleem kleiner maakt. Voor invoer waarvoor de berekening moet eindigen, moet elke aanroepketen een basisgeval bereiken. Alleen een stopvoorwaarde hebben is niet genoeg als de argumenten daar nooit aan voldoen.
In het voorbeeld berekent sum_to(5) de som van 1 tot en met 5. De aanroepen verlagen n totdat het 0 bereikt; bij de opeenvolgende terugkeer worden vervolgens de openstaande waarden opgeteld, wat 15 oplevert. Elke aanroep heeft een eigen parameter n; het is niet één gedeelde variabele. Voor n <= 0 geeft de functie 0 terug.
Beschouw het voorbeeld niet als een oplossing voor invoer van willekeurige grootte: diepe recursie kan uitvoeringsbronnen uitputten, en een som buiten het bereik van int leidt tot ongedefinieerd gedrag. Overweeg bij grote invoer een lus en bereikcontroles. De opgegeven bron is een evoluerend concept van een standaard, geen definitieve C++23-publicatie; het voorbeeld gebruikt syntaxis die compatibel is met C++23.
Voorbeelden
#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';
}
Resultaat
15
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.