Différence entre la récursivité et l'itération

Différence clé - Recursion vs itération
 

La récursivité et l'itération peuvent être utilisées pour résoudre les 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. Le différence clé 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. Aperçu 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 - Recursion vs itération sous forme tabulaire
6. Résumé

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

Lorsqu'une fonction s'appelle dans la fonction, elle est connue sous le nom de récursivité. Il existe deux types de récursités. Ils sont une récursion finie et une récursivité infinie. Récursivité finie a une condition de terminaison. Recursion infinie n'a pas de condition de terminaison.

La récursivité peut être expliquée en utilisant le programme pour calculer.

n! = n * (n-1)!, Si n> 0

n! = 1, si n = 0;

Reportez-vous au code ci-dessous pour calculer factoriel de 3 (3!= 3 * 2 * 1).

int main ()

int value = factoriel (3);

printf («factoriel est% d \ n», valeur);

retour 0;

intfactorial (intn)

if (n == 0)

retour 1;

autre

retour n * factoriel (n-1);

Lors de l'appel factoriel (3), cette fonction appellera factoriel (2). Lors de l'appel factoriel (2), cette fonction appellera factoriel (1). Alors factoriel (1) appellera factoriel (0). factoriel (0) reviendra 1. Dans le programme ci-dessus, n == 0 condition dans le «If Block» est la condition de base. Selon le 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 d'appel, 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. Donc, il crée un enregistrement d'activation ou un cadre de pile pour continuer l'exécution.

Figure 01: Recursion

Dans le programme ci-dessus, lors de l'appel factoriel (3) de Main, il crée un enregistrement d'activation dans la pile d'appels. Ensuite, la trame de pile factorielle (2) est créée sur le 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éée en haut de la pile. Ces cadres de pile peuvent ralentir la vitesse. De même dans la récursivité, une fonction s'appelle. La complexité du temps pour une fonction récursive est trouvée par le nombre de fois, la fonction est appelée.  La complexité du temps 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 «pour la boucle», la «boucle de faire» ou «while lobe». La syntaxe «For Loop» est la suivante.

pour (initialisation; condition; modifier) ​​

// instructions;

Figure 02: «Pour le diagramme de flux de boucle»

L'étape d'initialisation s'exécute d'abord. Cette étape consiste à déclarer et à initialiser les variables de contrôle de la boucle. Si la condition est vraie, les instructions à l'intérieur des accolades bouclées s'exécutent. Ces déclarations s'exécutent jusqu'à ce que la condition soit vraie. Si la condition est fausse, le contrôle passe à la déclaration suivante après la «boucle pour la boucle». Après avoir exécuté les instructions à l'intérieur de la boucle, le contrôle va à la section modifier. C'est pour mettre à jour la variable de contrôle de la boucle. Ensuite, la condition est à nouveau vérifiée. Si la condition est vraie, les instructions à l'intérieur des accolades bouclées s'exécuteront. De cette façon, la «Loop» itère.

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. Donc, la boucle exécute au moins une fois.

faire

// déclarations

tandis que (condition)

Programme pour trouver le factoriel de 3 (3!) Utilisation de l'itération («For Loop») est la suivante.

int main()

intn = 3, factoriel = 1;

Inti;

pour (i = 1; i<=n ; i++)

factoriel = factoriel * i;

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 soit en récursivité, soit en itération.

Quelle est la différence entre la récursivité et l'itération?

Résumé - Recursion vs itération

Cet article a discuté de la différence entre la récursivité et l'itération. Les deux peuvent être utilisés pour résoudre les 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 en utilisant des 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

Référence:

1.Point, tutoriels. «Structures de données et algorithmes Recursion Basics.», Tutorials Point, 15 août. 2017. Disponible ici 
2.nareshtechnologies. «Récursion en C fonctions | C Tutorial de langue ”YouTube, YouTube, 12 septembre. 2016.  Disponible ici  
3.Yusuf Shakeel. «Algorithme de récursivité | Factorial - Guide étape par étape »YouTube, YouTube, 14 octobre. 2013.  Disponible ici  

Image gracieuseté:

1.«CPT-Recursion-Factorial-Code» Pluke - Propre travaux, (domaine public) via Commons Wikimedia 
2.'For-Loop-Diagram'by Aucun auteur lisible par machine fourni - propre travail supposé. (CC BY-SA 2.5) Via Commons Wikimedia