Préface
J'ai vu ce contenu récemment quand je lisais un livre et je me sentais assez gratifiant. L'itération utilise une boucle (pour, bien que, wile) ou un itérateur, qui sort lorsque la condition de boucle n'est pas remplie. La récursivité est généralement une récursion de fonction, qui peut être appelée par elle-même ou par des appels non dirigés, c'est-à-dire la méthode A des appels Méthode B, et la méthode B des appels B à son tour, et la condition de sortie récursive est une instruction IF et ELONE, et quitte lorsque la condition répond à la base.
Ce qui précède est les caractéristiques de syntaxe de l'itération et de la récursivité. Quelles sont les différences entre eux en Java? Apprenez-nous plus sur cet article ci-dessous.
1. Recursion
En ce qui concerne l'itération, nous devons mentionner une expression mathématique: n!=n*(n-1)*(n-2)*...*1
Il existe de nombreuses façons de calculer les factoriels. Toute personne avec une certaine fondation mathématique sait n!=n*(n-1)! Par conséquent, l'implémentation du code peut être écrite directement comme:
Code 1
int factorial (int n) {if (n == 1) {return 1; } else {return n * factorial (n-1); }} Lors de l'exécution du code ci-dessus, la machine doit réellement effectuer une série de multiplications: factorial(n) → factorial(n-1) → factorial(n-2) →… → factorial(1) . Par conséquent, il est nécessaire de suivre (suivre le résultat du dernier calcul) et d'appeler la multiplication pour effectuer des calculs (construire une chaîne de multiplication). Ce type d'opération qui s'appelle constamment s'appelle Recursion. La récursivité peut être divisée en récursivité linéaire et en récursivité numérique. La quantité d'informations augmente linéairement avec l'entrée de l'algorithme. La récursivité est appelée récursivité linéaire. Calculez n! (Factory) est une récursivité linéaire. Étant donné que N augmente, le temps requis pour le calcul augmente linéairement. Un autre type d'informations qui se développe de façon exponentielle avec l'augmentation de l'entrée est appelée récursivité des arbres.
2. Itération
Une autre façon de calculer n! IS: Calculez d'abord 1 multiplier par 2, puis multipliez le résultat par 3, puis multipliez le résultat par 4 ... et multipliez jusqu'à N. Pendant la mise en œuvre du programme, un compteur peut être défini. Chaque fois que la multiplication est effectuée, le compteur est incrémenté une fois jusqu'à ce que la valeur du compteur soit égale à N. Le code est le suivant:
Code deux
int factorial (int n) {int product = 1; pour (int i = 2; i <n; i ++) {product * = i; } Retour Produit;}Comparé au code un, le code deux ne construit pas de chaîne de multiplication. Lorsque vous effectuez chaque étape de calcul, il vous suffit de connaître le résultat actuel (produit) et les valeurs de i. Cette forme de calcul est appelée itération. Il existe plusieurs conditions pour l'itération: 1. Il existe une variable avec une valeur initiale. 2. Une règle qui explique comment les valeurs variables sont mises à jour. 3. Une condition finale. (Trois éléments de la boucle: variables de boucle, corps de boucle et conditions de terminaison de boucle). Identique à la récursivité. Le temps qui devient linéaire à mesure que l'entrée augmente linéairement peut être appelé itération linéaire.
3. Itération contre la récursivité
Après avoir comparé les deux programmes, nous pouvons constater qu'ils se ressemblent presque, en particulier en termes de leurs fonctions mathématiques. Lors du calcul n!, Leurs étapes de calcul sont proportionnelles à la valeur de n. Cependant, si nous prenons le point de vue du programme et examinons comment ils fonctionnent, les deux algorithmes sont très différents.
(Remarque: le texte d'origine est un peu hors de propos quant à la différence, donc je ne le traduiserai pas ici. Ce qui suit est le propre résumé de l'auteur.)
Tout d'abord, analysez la récursivité. En fait, la chose la plus importante à propos de la récursivité est de décomposer un algorithme complexe en plusieurs étapes reproductibles identiques. Par conséquent, l'utilisation de la récursivité pour implémenter une logique de calcul ne nécessite souvent qu'un code très court pour résoudre, et un tel code est plus facile à comprendre. Cependant, la récursivité signifie un grand nombre d'appels de fonction. La raison pour laquelle l'état local d'un appel de fonction est enregistré à l'aide d'une pile. Par conséquent, cela peut gaspiller beaucoup d'espace, et si la récursivité est trop profonde, cela peut provoquer un débordement de pile.
Ensuite, analysez les itérations. En fait, la récursivité peut être remplacée par itération. Cependant, par rapport à la simplicité et à la compréhension de la récursivité, l'itération est plus rigide et difficile à comprendre. Surtout lors de la rencontre d'un scénario plus complexe. Cependant, la difficulté de comprendre le code apporte également des points plus évidents. L'efficacité de l'itération est plus élevée que la récursivité et est également relativement faible dans la consommation d'espace.
Il doit y avoir des itérations dans la récursivité, mais il n'y a peut-être pas de récursions dans les itérations, et la plupart d'entre elles peuvent être converties les unes aux autres.
Si vous pouvez utiliser l'itération, n'utilisez pas de récursivité. L'appel des fonctions récursivement non seulement gaspille l'espace, mais peut également facilement provoquer un débordement de pile si la récursivité est trop profonde.
4. Recursion des nombres
Comme mentionné précédemment, la quantité d'informations que l'arbre récursive augmente de façon exponentielle avec l'augmentation de l'entrée. La séquence Fibonacci est un exemple typique:
Dans la description du texte, la somme des deux premiers nombres de la séquence Fibonacci est égale au troisième nombre: 0, 1, 1, 2, 3, 5, 8, 13, 21 ...
Le code d'implémentation récursif est le suivant:
int fib (int n) {if (n == 0) {return 0; } else if (n == 1) {return 1; } else {return fib (n-1) + fib (n-2); }} Pendant le processus de calcul, afin de calculer fib(5) , le programme doit d'abord calculer fib(4) et fib(3) . Afin de calculer fib(4) , le programme doit également calculer d'abord fib(3) et fib(2) . FIB (3) est calculé deux fois au cours de ce processus.
À partir du processus de calcul analysé ci-dessus, nous pouvons tirer une conclusion: il y a un calcul redondant pour la mise en œuvre de la séquence de Fibonacci en utilisant la récursivité.
Comme mentionné ci-dessus, les algorithmes récursifs peuvent généralement être mis en œuvre par itérativement, et il en va de même pour les calculs de séquence Fibonacci.
int fib (int n) {int fib = 0; int a = 1; pour (int i = 0; i <n; i ++) {int temp = fib; fib = fib + a; a = temp; } return fib;}Bien qu'il y aura des calculs redondants dans la méthode de récursivité, il peut être remplacé par itération. Mais cela ne signifie pas que la récursivité peut être complètement remplacée. Parce que la récursivité a une meilleure lisibilité.
Résumer
Ce qui précède est l'intégralité du contenu de cet article. J'espère que le contenu de cet article sera utile à tout le monde dans l'apprentissage ou l'utilisation de Java. Si vous avez des questions, vous pouvez laisser un message pour communiquer.