Maîtriser la récursion en C++ : Concepts, exemples et bonnes pratiques

Maîtriser la récursion en C++

Dans ce tutoriel, nous explorerons les fonctions récursives en C++, comprendrons comment elles fonctionnent et verrons des exemples pratiques.

Une fonction qui s'appelle elle-même est appelée fonction récursive. Cette technique puissante est connue sous le nom de récursion.

---

Comment la récursion fonctionne en C++

void recursif() {
    // code pré-récursion
    recursif(); // appel récursif
    // code post-récursion
}

int main() {
    // code de configuration
    recursif();
    // code de nettoyage
}

La figure ci-dessous illustre la nature d'auto-appel répétée de la récursion.

La récursion continue jusqu'à ce qu'une condition de base soit satisfaite.

Pour éviter la récursion infinie, une garde conditionnelle (ex. if…else) assure qu'une seule branche effectue l'appel récursif.

---

Exemple 1 : Calcul du factoriel récursivement

// Calcule n! = 1 × 2 × … × n
#include <iostream>
using namespace std;

int factoriel(int);

int main() {
    int n, resultat;
    cout << "Entrez un nombre non-négatif : ";
    cin >> n;
    resultat = factoriel(n);
    cout << "Factoriel de " << n << " = " << resultat;
    return 0;
}

int factoriel(int n) {
    if (n > 1)
        return n * factoriel(n - 1);
    else
        return 1;
}

Sortie

Entrez un nombre non-négatif : 4
Factoriel de 4 = 24

---

Comment fonctionne le programme factoriel

La fonction factoriel() s'appelle répétitivement, réduisant n de un à chaque fois. Quand n tombe à 1 ou moins, la fonction retourne 1, et la récursion se déploie, produisant le résultat final.

---

Avantages et inconvénients de la récursion en C++

Voici les principaux avantages et inconvénients de la récursion.

---

Avantages

• Résulte en code concis et expressif.
• Essentiel pour des solutions naturelles aux problèmes impliquant arbres, graphes et recherche combinatoire.

---

Inconvénients

• Consomme plus d'espace de pile qu'une approche itérative équivalente.
• Peut engendrer une surcharge processeur additionnelle.
• Le débogage peut être plus difficile en raison de piles d'appels profondes.

---

En comprenant quand et comment utiliser la récursion, vous pouvez écrire du code C++ plus propre et plus maintenable tout en évitant les pièges courants.