Explication détaillée des exemples d'itération et de récursivité en Java

Cet article vous présente principalement l'itération et la récursion en Java L'article montre que introduit respectivement l'itération et la récursion, puis introduit l'itération et la récursion. le contenu associé à la récursion de la forme des nombres est présenté en détail dans l'article. Je pense qu'il aura une certaine valeur de référence pour l'étude de chacun. Les amis dans le besoin peuvent s'y référer.

Avant-propos

J'ai vu ce contenu en lisant un livre récemment, et cela m'a semblé assez gratifiant. L'itération utilise des boucles (for, while, do...wile) ou des itérateurs et se termine lorsque les conditions de la boucle ne sont pas remplies. La récursivité, généralement la récursion de fonction, peut s'appeler elle-même, ou il peut s'agir d'un appel indirect, c'est-à-dire que la méthode A appelle la méthode B et que la méthode B appelle à son tour la méthode A. Les conditions de sortie récursive sont instruction if, else , quittez lorsque la condition répond à la base.

Ce qui précède sont les caractéristiques grammaticales de l'itération et de la récursivité. Quelles sont leurs différences en Java ? Apprenez-en davantage à travers cet article ci-dessous.

1. Récursion

Quand il s'agit d'itération, je dois mentionner une expression mathématique : n!=n*(n-1)*(n-2)*...*1

Il existe de nombreuses façons de calculer une factorielle. Toute personne ayant une certaine base mathématique le sait n!=n*(n-1)! Par conséquent, l'implémentation du code peut être écrite directement :

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 en fait exécuter une Pour la multiplication en série : factorial(n) → factorial(n-1) → factorial(n-2) → … → factorial(1) . Par conséquent, il est nécessaire de suivre en permanence (suivre le résultat du dernier calcul) et d'appeler la multiplication pour le calcul (construire une chaîne de multiplication). Ce type d'opération qui s'appelle continuellement est appelé récursivité. La récursivité peut être divisée en récursivité linéaire et récursivité numérique. La récursion dans laquelle la quantité d'informations augmente linéairement avec l'entrée de l'algorithme est appelée récursion linéaire. Le calcul n! (factoriel) est une récursion linéaire. Car à mesure que N augmente, le temps nécessaire au calcul augmente linéairement. Un autre type d’informations qui augmente de façon exponentielle à mesure que l’entrée augmente est appelé récursivité arborescente.

2. Itération

Une autre façon de calculer n est : multipliez d'abord 1 par 2, puis multipliez le résultat par 3. Ensuite multipliez le résultat obtenu par 4... et multipliez-le jusqu'à N. Lors de l'implémentation du programme, vous pouvez définir un compteur. Chaque fois qu'une multiplication est effectuée, le compteur incrémentera jusqu'à ce que la valeur du compteur soit égale à N. Le code est le suivant :

Code 2

int factorial (int n) {
 int product = 1;
 for(int i=2; i<n; i++) {
  product *= i;
 }
 return product;
}

Par rapport au code 1, le code 2 ne construit pas de chaîne de multiplication. Lors de l'exécution de chaque étape du calcul, il vous suffit de connaître le résultat actuel (produit) et la valeur de i. Cette forme de calcul est appelée itération. Il y a plusieurs conditions pour l'itération : 1. Il existe une variable avec une valeur initiale. 2. Une règle qui décrit comment les valeurs des variables sont mises à jour. 3. Une condition finale. (Trois éléments d'une boucle : variables de boucle, corps de boucle et condition de fin de boucle). Identique à la récursion. Les exigences de temps qui augmentent linéairement avec les entrées peuvent être appelées itérations linéaires.

3. Itération VS Récursion

En comparant les deux programmes, on constate qu'ils se ressemblent presque, notamment leur aspect fonctions mathématiques. Lors du calcul de n!, leur nombre d'étapes de calcul est proportionnel à la valeur de n. Cependant, si l’on considère leur fonctionnement du point de vue du programme, les deux algorithmes sont alors très différents.

(Remarque : l'article original est un peu idiot à propos de la différence, je ne le traduirai donc pas ici. Ce qui suit est le propre résumé de l'auteur.)

Analysez d'abord la récursion en fait. , le plus grand avantage de la récursivité est qu'un algorithme complexe est décomposé en un certain nombre d'étapes identiques et répétables. Par conséquent, l’utilisation de la récursivité pour implémenter une logique de calcul ne nécessite souvent qu’un code court à résoudre, et un tel code est relativement facile à comprendre. Cependant, la récursivité implique de nombreux appels de fonctions. La raison pour laquelle l'état local des appels de fonction est enregistré à l'aide de la pile. Par conséquent, cela peut gaspiller beaucoup d’espace et provoquer un débordement de pile si la récursivité est trop profonde.

Ensuite, analysez les itérations. En fait, la récursivité peut être remplacée par l’itération. Mais comparée à la récursivité, qui est simple et facile à comprendre, l’itération est plus brutale et difficile à comprendre. Surtout face à une scène plus complexe. Cependant, les inconvénients apportés par la difficulté de compréhension du code sont également évidents. L'itération est plus efficace que la récursivité et consomme moins d'espace.

Il doit y avoir une itération dans la récursion, mais il peut ne pas y avoir de récursion dans l'itération, et la plupart d'entre elles peuvent être converties les unes dans les autres.

N'utilisez pas la récursivité si vous pouvez utiliser l'itération. Les fonctions d'appel récursives gaspillent non seulement de l'espace, mais provoquent également facilement un débordement de pile si la récursivité est trop profonde.

4. Récursion des nombres

前面介绍过，树递归随输入的增长的信息量呈指数级增长。比较典型的就是斐波那契数列：

用文字描述就是斐波那契数列中前两个数字的和等于第三个数字：0,1,1,2,3,5,8,13,21……

递归实现代码如下：

int fib (int n) {
 if (n == 0) {
  return 0;
 } else if (n == 1) {
  return 1;
 } else {
  return fib(n-1) + fib(n-2);
 }
}

计算过程中，为了计算fib(5) ，程序要先计算fib(4) 和 fib(3) ，要想计算fib(4) ，程序同样需要先计算 fib(3) 和 fib(2) 。在这个过程中计算了两次fib(3)。

从上面分析的计算过程可以得出一个结论：使用递归实现斐波那契数列存在冗余计算。

就像上面提到的，可以用递归的算法一般都能用迭代实现，斐波那契数列的计算也一样。

int fib (int n) {
 int fib = 0;
 int a = 1;
 for(int i=0; i<n; i++) {
  int temp = fib;
  fib = fib + a;
  a = temp;
 }
 return fib;
}

虽然使用递归的方式会有冗余计算，可以用迭代来代替。但是这并不表明递归可以完全被取代。因为递归有更好的可读性。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!