Menu

Récursivité en C ++

recursion c

Essayez Notre Instrument Pour Éliminer Les Problèmes

Découvrez tout sur la récursivité en C ++ avec des exemples classiques.

Dans notre didacticiel précédent, nous en avons appris davantage sur les fonctions en C ++.

Outre l'utilisation des fonctions pour décomposer le code en sous-unités et rendre le code plus simple et lisible, les fonctions sont utiles dans diverses autres applications, notamment la résolution de problèmes en temps réel, le calcul mathématique et statistique.

Au fur et à mesure que nous développons des applications plus complexes en C ++, nous rencontrons de nombreuses exigences et nous devons donc utiliser plusieurs concepts spéciaux de C ++. La récursivité est l'un de ces concepts.

=> Visitez ici pour la liste complète des didacticiels C ++.

RÉCURSION EN C ++

Dans ce didacticiel, nous en apprendrons davantage sur la récursivité, où et pourquoi elle est utilisée, avec quelques exemples C ++ classiques qui implémentent la récursivité.

Ce que vous apprendrez:

Qu'est-ce que la récursivité?

La récursivité est un processus dans lequel une fonction s'appelle elle-même. La fonction qui implémente la récursivité ou qui s'appelle elle-même est appelée une fonction récursive. En récursivité, la fonction récursive s'appelle elle-même encore et encore et continue jusqu'à ce qu'une condition de fin soit remplie.

L'image ci-dessous illustre le fonctionnement de la récursivité:

Fonctionnement de la récursivité

Comme nous le voyons dans le diagramme ci-dessus, la fonction principale appelle une fonction, funct (). La fonction funct () s'appelle à son tour dans sa définition. C'est ainsi que fonctionne la récursivité. Ce processus de l'appel de la fonction se poursuivra jusqu'à ce que nous fournissions une condition de fin qui la fera se terminer.

Habituellement, nous fournissons une branche de code lors de l'implémentation de la récursivité de sorte que nous fournissons une condition qui déclenchera la récursivité et une autre pour effectuer une exécution normale.

Condition de base de récursivité

Lorsque la récursivité est effectuée, la solution au cas de base ou au cas de terminaison est fournie et les solutions aux problèmes plus importants sont construites sur la base des solutions aux problèmes plus petits.

Prenons un exemple classique de récursivité, la notation factorielle.

Nous savons que mathématiquement la factorielle d'un nombre n est:

n! = nxn-1x… .x0!
étant donné que 0! = 1;

Donc factoriel pour n = 3 sera 3! = 3 × 2!

3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6

Donc, par programmation, nous pouvons exprimer ce calcul comme suit:

int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }

Ainsi, comme indiqué ci-dessus, nous avons exprimé le calcul ci-dessus d'une factorielle en un appel de fonction récursive. On voit que si le nombre n est inférieur ou égal à 1, on renvoie 1 au lieu d'un appel récursif. C'est ce qu'on appelle la condition / le cas de base pour la factorielle qui permet d'arrêter la récursivité.

Par conséquent, la condition de base décide essentiellement combien de fois une fonction récursive doit s'appeler elle-même. Cela signifie que nous pouvons très bien calculer la factorielle d'un plus grand nombre en l'exprimant en termes de nombres plus petits jusqu'à ce que la classe de base soit atteinte.

Ci-dessous est un exemple parfait pour calculer la factorielle d'un nombre:

#include #include using namespace std; int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); } int main() { int num,result; cout<>num; result = factorial(num); cout<

Production:

Entrez le nombre dont la factorielle doit être calculée: 10
dix! = 3628800

Dans l'exemple ci-dessus, nous implémentons la récursivité. Nous prenons le nombre dont la factorielle doit être trouvée à partir de l'entrée standard et le passons ensuite à la fonction factorielle.

Dans la fonction factorielle, nous avons donné la condition de base comme (n<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.

Allocation de mémoire pour l'appel récursif

Nous savons que lorsqu'un appel de fonction est effectué, l'état de la fonction appelante est stocké sur la pile et lorsqu'un appel de fonction est terminé, cet état est restauré afin que le programme puisse continuer l'exécution.

Lorsqu'un appel de fonction récursif est effectué, l'état ou la mémoire de la fonction appelée est allouée en plus de l'état de la fonction appelante et une copie différente des variables locales est effectuée pour chaque appel de fonction récursive.

Lorsque la condition de base est atteinte, la fonction retourne à la fonction appelante et la mémoire est désallouée et le processus se poursuit.

Dépassement de pile dans la récursivité

Lorsque la récursivité se poursuit pendant une durée illimitée, cela peut entraîner un débordement de pile.

Quand la récursivité peut-elle continuer comme ça? Une situation est celle où nous ne spécifions pas la condition de base. Une autre situation est lorsque la condition de base n'est pas atteinte lors de l'exécution d'un programme.

Par exemple,nous modifions le programme factoriel ci-dessus et changeons sa condition de base.

int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }

Dans le code ci-dessus, nous avons changé la condition de base en (n == 1000). Maintenant, si nous donnons le nombre n = 10, nous pouvons conclure que la condition de base n'atteindra jamais. De cette façon, à un moment donné, la mémoire de la pile sera épuisée, ce qui entraînera un débordement de pile.

Par conséquent, lors de la conception de programmes récursifs, nous devons faire attention à la condition de base que nous fournissons.

Récursivité directe vs indirecte

Jusqu'à présent, en récursivité, nous avons vu la fonction s'appeler elle-même. C'est la récursion directe.

Il existe un autre type de récursivité, à savoir la récursivité indirecte. En cela, une fonction appelle une autre fonction, puis cette fonction appelle la fonction appelante. Si f1 et f2 sont deux fonctions. Puis f1 appelle f2 et f2, à son tour, appelle f1. C'est une récursion indirecte.

jointure intérieure jointure gauche jointure droite

L et nous révisons notre programme factoriel pour démontrer la récursivité directe.

#include #include using namespace std; int factorial_b(int); int factorial_a(int n){ if(n <=1) return 1; else return n*factorial_b(n-1); } int factorial_b(int n){ if(n <=1) return 1; else return n*factorial_a(n-1); } int main() { int num, result; cout<>num; result = factorial_a(num); cout<

Production:

Entrez le nombre dont la factorielle doit être calculée: 5
5! = 120

Dans l'exemple ci-dessus, nous avons montré la récursivité indirecte. La fonction principale appelle factorial_a. Factorial_a appelle factorial_b. A son tour factorial_b appelle factorial_a. On voit que la sortie du programme n'est pas affectée.

Récursivité avec et sans queue

Une fonction récursive à queue est une fonction récursive où le dernier appel est exécuté dans la fonction.

Par exemple, considérez la fonction suivante.

void display(int n){ if(n<=1) return; cout<<” ”<

Dans l'exemple ci-dessus, l'affichage est une fonction récursive à queue telle qu'il s'agit du dernier appel de fonction.

Les fonctions avec queue sont considérées comme meilleures que les fonctions récursives sans queue car elles peuvent être optimisées par le compilateur. La raison en est que comme l'appel récursif avec queue est la dernière instruction de la fonction, il n'y a pas de code à exécuter après cet appel.

Par conséquent, il n'est pas nécessaire d'enregistrer le cadre de pile actuel pour la fonction.

Avantages / inconvénients de la récursivité par rapport à la programmation itérative

Les programmes récursifs fournissent un code compact et propre. Un programme récursif est un moyen simple d'écrire des programmes. Il existe des problèmes inhérents tels que factoriel, séquence de Fibonacci, tours de Hanoi, traversées d'arbres, etc. qui nécessitent une récursivité pour être résolus.

En d'autres termes, ils sont résolus efficacement avec la récursivité. Ils peuvent également être résolus avec une programmation itérative utilisant des piles ou d'autres structures de données, mais il y a des chances de devenir plus complexes à mettre en œuvre.

Les pouvoirs de résolution de problèmes de la programmation récursive et itérative sont les mêmes. Cependant, les programmes récursifs prennent plus d'espace mémoire car tous les appels de fonction doivent être stockés sur la pile jusqu'à ce que le cas de base soit mis en correspondance.

Les fonctions récursives ont également une surcharge de temps en raison d'un trop grand nombre d'appels de fonction et de valeurs de retour.

Exemples de récursivité

Ensuite, nous mettrons en œuvre certains des exemples de programmation récursive.

Série Fibonacci

La série de Fibonacci est la séquence donnée par

0 1 1 2 3 5 8 13 ……

Comme indiqué ci-dessus, les deux premiers nombres de la série de Fibonacci sont 0 et 1. Le nombre suivant dans la séquence est la somme des deux nombres précédents.

Implémentons cette série en utilisant la récursivité.

#include using namespace std; void fibSeries(int n){ static int n1=0, n2=1, n3; if(n>0){ n3 = n1 + n2; n1 = n2; n2 = n3; cout<num; cout<<'Fibonacci Series for '<

Production:

Entrez le nombre d'éléments pour la série Fibonacci: 10
Série Fibonacci pour 10 numéros: 0 1 1 2 3 5 8 13 21 34

Dans cet exemple, nous avons utilisé un appel récursif pour générer la séquence de Fibonacci. On voit que les deux premiers nombres constants sont directement imprimés et pour les nombres suivants de la séquence on utilise une fonction récursive.

Palindrome

Un nombre palindrome est un nombre qui, lorsqu'il est lu en sens inverse, est le même que celui lu de gauche à droite.

Par exemple, le nombre 121 en lisant de gauche à droite et de droite à gauche se lit le même, c'est-à-dire 121. Par conséquent, 121 est un palindrome.

Le nombre 291, lors de la lecture de droite à gauche, c'est-à-dire dans l'ordre inverse, se lit comme 192. Par conséquent, 291 n'est pas un palindrome.

#include using namespace std; int reverse_digits(int n, int temp) { if (n == 0) return temp; temp = (temp * 10) + (n % 10); return reverse_digits(n / 10, temp); } int main() { int num; cout<>num; int result = reverse_digits(num, 0); if (result == num) cout << 'Number '<

Production:

Entrez le numéro pour vérifier le palindrome: 6556
Le numéro 6556 est un palindrome

Une capture d'écran pour le même est donnée ci-dessous.

Récursion - Palindrome

Dans le programme ci-dessus, nous lisons le numéro d'entrée à partir de l'entrée standard. Ensuite, nous passons ce nombre à une fonction récursive pour inverser les chiffres d'un nombre. Si les chiffres inversés et le numéro d'entrée sont identiques, le numéro est un palindrome.

Conclusion

Avec cela, nous en avons terminé avec la récursivité. Dans ce tutoriel, nous avons étudié la programmation récursive, la fonction récursive, ses avantages / inconvénients, ainsi que divers exemples en détail.

En dehors de ces exemples, la récursivité est également utilisée pour résoudre certains problèmes standard tels que les traversées (en ordre / précommande / post-commande), les tours de Hanoi, la traversée BFS, etc.

=> Visitez ici pour apprendre le C ++ à partir de zéro.

lecture recommandée

^