Différence entre récursivité et itération

Différence clé - Récursion 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 en utilisant la récursivité ou l’itération dépend de la façon de résoudre le problème. le différence clé entre récursion et itération est que La récursivité est un mécanisme permettant d'appeler une fonction dans 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 le développement d'algorithmes et la construction d'applications logicielles.

CONTENU

1. Vue d'ensemble et différence clé
2. Quelle est la récursion
3. Quelle est l'itération
4. Similitudes entre la récursivité et l'itération
5. Comparaison côte à côte - Récursion vs Itération sous forme tabulaire
6. Résumé

Quelle est la récursion?

Quand une fonction s’appelle dans la fonction, elle est appelée récursivité. Il existe deux types de récursivité. Ils sont récursion finie et récursion infinie. Récursion finie a une condition de terminaison. Récursion infinie n'a pas de condition finale.

La récursivité peut être expliquée à l'aide du programme permettant de calculer des 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 ()

int = factorielle (3);

printf (“Factorial is% d \ n”, valeur);

retourne 0;

intfactorial (intn)

si (n == 0)

retourne 1;

autre

retourne n * factorielle (n-1);

Lorsque vous appelez factorielle (3), cette fonction appellera factorielle (2). Lorsque vous appelez factorielle (2), cette fonction appellera factorielle (1). Ensuite factoriel (1) appellera factorial (0). factorielle (0) retournera 1. Dans le programme ci-dessus, la condition n == 0 dans «if block» est la condition de base. 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. Donc, 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 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: Récursion

Dans le programme ci-dessus, lorsqu’il appelle factorial (3) depuis main, il crée un enregistrement d’activation dans la pile d’appels. Ensuite, un cadre de pile factoriel (2) est créé en haut de la pile, etc. 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écursion, 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 d'un appel de fonction est O (1). Pour n nombre d'appels récursifs, la complexité temporelle est O (n).

Quelle est 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.

pour (initialisation; condition; modifier) ​​

// déclarations;

Figure 02: «diagramme de flux de 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 sont exécutées. Ces déclarations sont exécutées 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 va modifier la section. C'est pour mettre à jour la variable de contrôle de 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" itère.

En “boucle en boucle”, les instructions à l'intérieur de la boucle s'exécutent jusqu'à ce que la condition soit vraie.

while (condition)

// déclarations

En 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

tant que (condition)

Programme pour trouver la factorielle de 3 (3!) En utilisant l'itération ("pour la boucle") est la suivante.

int main()

intn = 3, factorielle = 1;

inti;

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

factorielle = factorielle * i;

printf (“Factorial is% d \ n”, factoriel);

retourne 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écurrence ou en itération.

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

Récursion vs Itération
La récursivité est une méthode permettant d’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.
La complexité de l'espace
La complexité spatiale des programmes récursifs est supérieure aux 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écursion, 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écursion 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 des problèmes de programmation. La différence entre récursivité et itération réside dans le fait 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 à 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écharger 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, conformément à la note de citation. Veuillez télécharger la version PDF ici Différence entre récursivité et itération

Référence:

1.Point, tutoriels. «Notions de base sur la récursion des structures de données et des algorithmes»., Tutoriels Point, 15 août 2017. Disponible ici 
2.nareshtechnologies. “Récursion dans les fonctions C | Tutoriel en langage C ”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  

Courtoisie d'image:

1.'CPT-Recursion-Factorial-Code'By Pluke - Travail personnel, (Domaine public) via Wikimedia Commons 
2. 'For-loop-diagram'By Aucun auteur lisible par machine n'a été fourni - Propre travail supposé. (CC BY-SA 2.5) via Wikimedia Commons