Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C++

Récursion

La récursion consiste pour une fonction à s’appeler elle-même, directement ou par l’intermédiaire d’autres fonctions. Pour que le calcul se termine, il lui faut un cas de base accessible et des étapes récursives qui progressent vers ce cas.

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

Syntaxe

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

La récursion (recursion) est une technique dans laquelle une fonction s’appelle elle-même, directement ou indirectement par l’intermédiaire d’autres fonctions. Elle ne nécessite aucun mot-clé spécial : elle utilise la syntaxe ordinaire des appels de fonction. C++ autorise les appels récursifs, mais main ne doit pas être appelée récursivement.

Un algorithme typique comporte un cas de base, qui renvoie un résultat sans effectuer un autre appel, et une étape récursive, qui réduit le problème. Pour les données qui doivent mener à la fin du calcul, chaque chaîne d’appels doit atteindre un cas de base. Avoir simplement une condition d’arrêt ne suffit pas si les arguments ne la satisfont jamais.

Dans l’exemple, sum_to(5) calcule la somme de 1 à 5 inclus. Les appels diminuent n jusqu’à ce qu’il atteigne 0 ; les retours successifs additionnent alors les valeurs en attente, ce qui donne 15. Chaque appel possède son propre paramètre n ; il ne s’agit pas d’une variable partagée unique. Pour n <= 0, la fonction renvoie 0.

Ne considère pas l’exemple comme une solution pour des données de taille arbitraire : une récursion profonde peut épuiser les ressources d’exécution, et une somme située hors de la plage de int entraîne un comportement indéfini. Pour de grandes données, envisage une boucle et des vérifications de plage. La source indiquée est un projet de norme en évolution, et non une publication C++23 figée ; l’exemple utilise une syntaxe compatible avec C++23.

Exemples

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

Résultat

15

Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.

Sources