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 pour appeler une fonction dans la même fonction, tandis que l'itération consiste à exécuter un ensemble d'instructions à plusieurs reprises 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.
CONTENU
1. Présentation et différence clé
2. Qu'est-ce que la récursivité
3. Qu'est-ce que l'itération
4. Similitudes entre la récursivité et l'itération
5. Comparaison côte à côte - Récursivité vs itération sous forme tabulaire
6. Résumé
Qu'est-ce que la récursivité?
Lorsqu'une fonction s'appelle elle-même dans la fonction, elle est appelée récursivité. Il existe deux types de récursivité. Ce sont une récursion finie et une récursion infinie. La récursivité finie a une condition de fin. La récursivité infinie n'a pas de condition de fin.
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! = 3 * 2 * 1).
int main () {
valeur int = factorielle (3);
printf («Factorielle est% d / n», valeur);
return 0;
}
intfactorial (intn) {
si (n == 0) {
return 1;
}
autre {
retourne n * factorielle (n-1);
}
}
Lors de l'appel de factorial (3), cette fonction appellera factorial (2). Lors de l'appel de factorial (2), cette fonction appellera factorial (1). Alors factorielle (1) appellera factorielle (0). factorial (0) renverra 1. Dans le programme ci-dessus, n == 0 condition dans le «si bloc» 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 qui est 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 est renvoyé à 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 factorial (3) depuis main, il crée un enregistrement d'activation dans la pile d'appels. Ensuite, un cadre de pile factorielle (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 que la fonction est appelée. La complexité temporelle pour un appel de fonction est O (1). Pour n nombre d'appels récursifs, la complexité temporelle est O (n).
Qu'est-ce que l'itération?
L'itération 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; modifier) {
// déclarations;
}
Figure 02: «pour le diagramme de flux de la boucle»
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 boucle. Ensuite, la condition est à nouveau vérifiée. Si la condition est vraie, les instructions à l'intérieur des accolades s'exécuteront. De cette façon, la «boucle for» est itérée.
Dans «while loop», les instructions à l'intérieur de la boucle s'exécutent jusqu'à ce que la condition soit vraie.
while (condition) {
// déclarations
}
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{
// déclarations
} while (condition)
Le programme pour trouver la factorielle de 3 (3!) En utilisant l'itération («boucle for») est le suivant.
int main(){
intn = 3, factoriel = 1;
inti;
pour (i = 1; i <= n; i ++) {
factorielle = factorielle * i;
}
printf («Factorielle est% d / n», factorielle);
return 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 soit par récursion, soit par itération.
Quelle est la différence entre la récursivité et l'itération?
Diff article au milieu avant la table
Récursivité vs itération |
|
| La récursivité est une méthode pour appeler 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 plus élevée que les itérations. | La complexité de l'espace est plus faible dans les itérations. |
| La 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écursion infinie. | Si la condition ne devient jamais fausse, ce sera une itération infinie. |
| Empiler | |
| En récursivité, la pile est utilisée pour stocker des 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 pour appeler une fonction dans la même fonction et l'itération pour exécuter un ensemble d'instructions à plusieurs reprises 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 à l'aide d'itérations.
Téléchargez la version PDF de Recursion vs Itération
Vous pouvez télécharger la version PDF de cet article et l'utiliser à des fins hors ligne selon la note de citation. Veuillez télécharger la version PDF ici Différence entre la récursivité et l'itération
