Différence clé - Récursivité vs Itération
La récursivité et l'itération peuvent être utilisées pour résoudre des problèmes de programmation. L'approche pour résoudre le problème à l'aide de la récursivité ou de l'itération dépend de la manière de résoudre le problème. La principale différence entre la récursivité et l'itération est que la récursivité est un mécanisme permettant d'appeler une fonction au sein de la même fonction, tandis que l'itération consiste à exécuter un ensemble d'instructions de manière répétée jusqu'à ce que la condition donnée soit vraie. La récursivité et l'itération sont des techniques majeures pour développer des algorithmes et créer des applications logicielles.
Qu'est-ce que la récursivité ?
Lorsqu'une fonction s'appelle elle-même dans la fonction, on parle de récursivité. Il existe deux types de récursivité. Ce sont la récursivité finie et la récursivité infinie. La récursivité finie a une condition de terminaison. La récursivité infinie n'a pas de condition de terminaison.
La récursivité peut être expliquée en utilisant le programme pour calculer les factorielles.
n !=n(n-1)!, si n>0
n !=1, si n=0;
Reportez-vous au code ci-dessous pour calculer la factorielle de 3(3!=321).
intmain() {
int valeur=factorielle (3);
printf("Factoriel est %d\n", valeur);
retour 0;
}
intfactoriel (intn) {
si(n==0) {
retour 1;
}
else {
return n factoriel(n-1);
}
}
Lors de l'appel de la factorielle (3), cette fonction appellera la factorielle (2). Lors de l'appel de la factorielle (2), cette fonction appellera la factorielle (1). Alors la factorielle (1) appellera la factorielle (0). la factorielle (0) renverra 1. Dans le programme ci-dessus, la condition n==0 dans le « bloc if » est la condition de base. Selon le De même, la fonction factorielle est appelée encore et encore.
Les fonctions récursives sont liées à la pile. En C, le programme principal peut avoir de nombreuses fonctions. Ainsi, main () est la fonction appelante et la fonction appelée par le programme principal est la fonction appelée. Lorsque la fonction est appelée, le contrôle est donné à la fonction appelée. Une fois l'exécution de la fonction terminée, le contrôle revient à main. Ensuite, le programme principal continue. Ainsi, il crée un enregistrement d'activation ou un cadre de pile pour continuer l'exécution.
Figure 01: Récursivité
Dans le programme ci-dessus, lors de l'appel de la factorielle (3) depuis main, il crée un enregistrement d'activation dans la pile des appels. Ensuite, un cadre de pile factoriel (2) est créé au-dessus de la pile et ainsi de suite. L'enregistrement d'activation conserve des informations sur les variables locales, etc. Chaque fois que la fonction est appelée, un nouvel ensemble de variables locales est créé en haut de la pile. Ces cadres de pile peuvent ralentir la vitesse. De même en récursivité, une fonction s'appelle elle-même. La complexité temporelle d'une fonction récursive est déterminée par le nombre de fois où la fonction est appelée. La complexité temporelle pour un appel de fonction est O(1). Pour un nombre n d'appels récursifs, la complexité temporelle est O(n).
Qu'est-ce que l'itération ?
Iteration est un bloc d'instructions qui se répète encore et encore jusqu'à ce que la condition donnée soit vraie. L'itération peut être réalisée en utilisant "for loop", "do-while loop" ou "while loop". La syntaxe "for loop" est la suivante.
for (initialisation; condition; modification) {
// déclarations;
}
Figure 02: "for loop flow diagram"
L'étape d'initialisation s'exécute en premier. Cette étape consiste à déclarer et initialiser les variables de contrôle de boucle. Si la condition est vraie, les instructions à l'intérieur des accolades s'exécutent. Ces instructions s'exécutent jusqu'à ce que la condition soit vraie. Si la condition est fausse, le contrôle passe à l'instruction suivante après la « boucle for ». Après avoir exécuté les instructions à l'intérieur de la boucle, le contrôle passe à la section de modification. Il s'agit de mettre à jour la variable de contrôle de la boucle. Ensuite, la condition est vérifiée à nouveau. Si la condition est vraie, les instructions à l'intérieur des accolades seront exécutées. De cette façon, la "boucle for" itère.
Dans "while loop", les instructions à l'intérieur de la boucle s'exécutent jusqu'à ce que la condition soit vraie.
tandis que (état){
//instructions
}
Dans la boucle "do-while", la condition est vérifiée à la fin de la boucle. Ainsi, la boucle s'exécute au moins une fois.
faire{
//instructions
} tandis que(condition)
Le programme pour trouver la factorielle de 3 (3 !) en utilisant l'itération ("for loop") est le suivant.
int main(){
intn=3, factorielle=1;
inti;
for(i=1; i<=n; i++){
factorielle=factoriellei;
}
printf("Factoriel est %d\n", factoriel);
retour 0;
}
Quelles sont les similitudes entre la récursivité et l'itération ?
- Les deux sont des techniques pour résoudre un problème.
- La tâche peut être résolue en récursivité ou en itération.
Quelle est la différence entre la récursivité et l'itération ?
Récursivité vs itération |
|
| La récursivité est une méthode d'appel d'une fonction dans la même fonction. | L'itération est un bloc d'instructions qui se répète jusqu'à ce que la condition donnée soit vraie. |
| Complexité spatiale | |
| La complexité spatiale des programmes récursifs est supérieure à celle des itérations. | La complexité de l'espace est plus faible dans les itérations. |
| Vitesse | |
| L'exécution de la récursivité est lente. | Normalement, l'itération est plus rapide que la récursivité. |
| État | |
| S'il n'y a pas de condition de terminaison, il peut y avoir une récursivité infinie. | Si la condition ne devient jamais fausse, ce sera une itération infinie. |
| Pile | |
| En récursivité, la pile est utilisée pour stocker les variables locales lorsque la fonction est appelée. | Dans une itération, la pile n'est pas utilisée. |
| Lisibilité du code | |
| Un programme récursif est plus lisible. | Le programme itératif est plus difficile à lire qu'un programme récursif. |
Résumé – Récursivité vs Itération
Cet article traite de la différence entre la récursivité et l'itération. Les deux peuvent être utilisés pour résoudre des problèmes de programmation. La différence entre la récursivité et l'itération est que la récursivité est un mécanisme permettant d'appeler une fonction dans la même fonction et de l'itérer pour exécuter un ensemble d'instructions de manière répétée jusqu'à ce que la condition donnée soit vraie. Si un problème peut être résolu sous forme récursive, il peut également être résolu en utilisant des itérations.
Télécharger la version PDF de Récursivité vs Itération
Vous pouvez télécharger la version PDF de cet article et l'utiliser à des fins hors ligne conformément à la note de citation. Veuillez télécharger la version PDF ici Différence entre la récursivité et l'itération
