Tableau de comparaison
| Base de comparaison | Récursion | Itération |
|---|---|---|
| De base | L'instruction dans un corps de fonction appelle la fonction elle-même. | Permet à l'ensemble d'instructions d'être exécuté de manière répétée. |
| Format | En fonction récursive, seule la condition de terminaison (cas de base) est spécifiée. | L'itération comprend l'initialisation, la condition, l'exécution de l'instruction dans la boucle et la mise à jour (incréments et décréments) de la variable de contrôle. |
| Résiliation | Une instruction conditionnelle est incluse dans le corps de la fonction pour forcer le retour de la fonction sans appel récursif en cours d'exécution. | L'instruction d'itération est exécutée à plusieurs reprises jusqu'à ce qu'une certaine condition soit atteinte. |
| État | Si la fonction ne converge pas vers une condition appelée (cas de base), cela conduit à une récursion infinie. | Si la condition de contrôle dans la déclaration d'itération ne devient jamais fausse, elle conduit à une itération infinie. |
| Répétition infinie | Une récursion infinie peut planter le système. | La boucle infinie utilise les cycles du processeur à plusieurs reprises. |
| Appliqué | La récursivité est toujours appliquée aux fonctions. | L'itération est appliquée aux instructions d'itération ou "boucles". |
| Empiler | La pile est utilisée pour stocker l'ensemble des nouvelles variables et paramètres locaux chaque fois que la fonction est appelée. | N'utilise pas de pile. |
| Aérien | La récursion possède la surcharge des appels de fonction répétés. | Pas de surcharge d'un appel de fonction répété. |
| La vitesse | Lente dans l'exécution. | Rapide dans l'exécution. |
| Taille du code | La récursivité réduit la taille du code. | L'itération allonge le code. |
Définition de récursion
C ++ permet à une fonction de s’appeler dans son code. Cela signifie que la définition de la fonction possède un appel de fonction à elle-même. Parfois, on l'appelle aussi « définition circulaire ». L'ensemble de variables locales et de paramètres utilisés par la fonction est créé à chaque fois que la fonction s'appelle elle-même et est stockée en haut de la pile. Toutefois, chaque fois qu’une fonction s’appelle elle-même, elle ne crée pas une nouvelle copie de cette fonction. La fonction récursive ne réduit pas significativement la taille du code et n'améliore même pas l'utilisation de la mémoire, mais en réduit quelque peu par rapport à l'itération.
Pour mettre fin à la récursivité, vous devez inclure une instruction select dans la définition de la fonction afin de forcer le renvoi de la fonction sans se lancer d'appel récursif. L'absence de l'instruction select dans la définition d'une fonction récursive laissera la fonction en récurrence infinie une fois appelée.
Comprenons la récursion avec une fonction qui retournera la factorielle du nombre.
int factorielle (int num) {int answer; si (num == 1) {retourne 1; } else {answer = factorial (num-1) * num; // appel récursif} return (answer); } Dans le code ci-dessus, l'instruction dans la partie else indique la récursivité, car elle appelle la fonction factorial () dans laquelle elle réside.
Définition de l'itération
L'itération est un processus d'exécution répétée du jeu d'instructions jusqu'à ce que la condition dans la déclaration d'itération devienne fausse. L'instruction d'itération inclut l'initialisation, la comparaison, l'exécution des instructions contenues dans l'instruction d'itération et enfin la mise à jour de la variable de contrôle. Une fois la variable de contrôle mise à jour, elle est à nouveau comparée et le processus se répète jusqu'à ce que la condition dans l'instruction itération devienne fausse. Les instructions d'itération sont boucle "for", boucle "while", boucle "do-while".
L'instruction d'itération n'utilise pas de pile pour stocker les variables. Par conséquent, l'exécution de l'instruction d'itération est plus rapide que la fonction récursive. Même la fonction d'itération n'a pas la surcharge d'appels de fonction répétés qui rendent également son exécution plus rapide que la fonction récursive. L'itération est terminée lorsque la condition de contrôle devient fausse. L'absence de condition de contrôle dans l'instruction d'itération peut entraîner une boucle infinie ou une erreur de compilation.
Comprenons l'itération concernant l'exemple ci-dessus.
int factorielle (int num) {int answer = 1; // nécessite une initialisation, car il peut contenir une valeur d'erreur avant son initialisation pour (int t = 1; t> num; t ++) // itération {answer = answer * (t); retour (réponse); }} Dans le code ci-dessus, la fonction renvoie la factorielle du nombre à l’aide d’une instruction d’itération.
Principales différences entre la récursivité et l'itération
- La récursivité se produit lorsqu'une méthode d'un programme s'appelle de manière répétée alors que l'itération est lorsqu'un ensemble d'instructions d'un programme est exécuté de manière répétée.
- Une méthode récursive contient un ensemble d’instructions, une instruction s’appelant elle-même et une condition de terminaison, tandis que les instructions d’itération contiennent l’initialisation, l’incrément, la condition, l’ensemble d’instructions dans une boucle et une variable de contrôle.
- Une instruction conditionnelle décide de la fin de la récursion et la valeur de la variable de contrôle décide de la fin de la déclaration d'itération.
- Si la méthode ne conduit pas à la condition de terminaison, elle entre en récursion infinie. D'autre part, si la variable de contrôle ne conduit jamais à la valeur de terminaison, l'instruction itération itère à l'infini.
- Une récursion infinie peut entraîner un crash du système, tandis qu'une itération infinie consomme des cycles de processeur.
- La récursivité est toujours appliquée à la méthode, tandis que l'itération est appliquée au jeu d'instructions.
- Les variables créées lors de la récursivité sont stockées sur une pile alors que l'itération ne nécessite pas de pile.
- La récursivité entraîne la surcharge des appels de fonction répétés, tandis que l'itération n'a pas de surcharge d'appel de fonction.
- En raison de l'appel des fonctions, le temps système nécessaire à l'exécution de la récursivité est plus lent, alors que l'exécution de l'itération est plus rapide
- La récursivité réduit la taille du code alors que les itérations allongent le code.
Conclusion:
La fonction récursive est facile à écrire, mais leur performance est médiocre par rapport à une itération, alors que l’itération est difficile à écrire, mais leur performance est bonne par rapport à la récursion.
