Récursivité C++
Récursivité C++
Dans ce didacticiel, nous allons découvrir la fonction récursive en C++ et son fonctionnement à l'aide d'exemples.
Une fonction qui s'appelle elle-même est appelée fonction récursive. Et cette technique est connue sous le nom de récursivité.
Fonctionnement de la récursivité en C++
void recurse()
{
... .. ...
recurse();
... .. ...
}
int main()
{
... .. ...
recurse();
... .. ...
} La figure ci-dessous montre comment fonctionne la récursivité en s'appelant encore et encore.
La récursivité continue jusqu'à ce qu'une condition soit remplie.
Pour éviter une récursivité infinie, l'instruction if...else (ou une approche similaire) peut être utilisée lorsqu'une branche effectue l'appel récursif et l'autre non.
Exemple 1 :Factorielle d'un nombre utilisant la récursivité
// Factorial of n = 1*2*3*...*n
#include <iostream>
using namespace std;
int factorial(int);
int main() {
int n, result;
cout << "Enter a non-negative number: ";
cin >> n;
result = factorial(n);
cout << "Factorial of " << n << " = " << result;
return 0;
}
int factorial(int n) {
if (n > 1) {
return n * factorial(n - 1);
} else {
return 1;
}
} Sortie
Enter a non-negative number: 4 Factorial of 4 = 24
Fonctionnement du programme factoriel
Comme nous pouvons le voir, le factorial() la fonction s'appelle elle-même. Cependant, lors de chaque appel, nous avons diminué la valeur de n par 1 . Quand n est inférieur à 1 , le factorial() la fonction renvoie finalement la sortie.
Avantages et inconvénients de la récursivité
Vous trouverez ci-dessous les avantages et les inconvénients de l'utilisation de la récursivité en C++.
Avantages de la récursivité C++
- Cela rend notre code plus court et plus clair.
- La récursivité est nécessaire dans les problèmes concernant les structures de données et les algorithmes avancés, tels que le parcours de graphes et d'arbres.
Inconvénients de la récursivité C++
- Cela prend beaucoup d'espace dans la pile par rapport à un programme itératif.
- Il utilise plus de temps processeur.
- Il peut être plus difficile à déboguer par rapport à un programme itératif équivalent.
Langue C