Est-il correct de dire que partout où la récursivité est utilisée, une forboucle pourrait être utilisée? Et si la récursivité est généralement plus lente, quelle est la raison technique de son utilisation sur forune itération de boucle?

Et s'il est toujours possible de convertir une récursion en forboucle, y a-t-il une règle empirique pour le faire?

La récursivité est généralement beaucoup plus lente car tous les appels de fonction doivent être stockés dans une pile pour permettre le retour aux fonctions appelantes. Dans de nombreux cas, la mémoire doit être allouée et copiée pour implémenter l'isolation de la portée.

Certaines optimisations, comme l' optimisation des appels de fin , accélèrent les récursions mais ne sont pas toujours possibles et ne sont pas implémentées dans toutes les langues.

Les principales raisons d'utiliser la récursivité sont

• qu'il est plus intuitif dans de nombreux cas lorsqu'il imite notre approche du problème
• que certaines structures de données comme les arbres sont plus faciles à explorer en utilisant la récursivité (ou auraient besoin de piles dans tous les cas)

Bien sûr, chaque récursivité peut être modélisée comme une sorte de boucle: c'est ce que le CPU fera finalement. Et la récursivité elle-même, plus directement, signifie placer les appels de fonction et les portées dans une pile. Mais changer votre algorithme récursif en un algorithme en boucle peut nécessiter beaucoup de travail et rendre votre code moins maintenable: comme pour chaque optimisation, il ne devrait être tenté que lorsqu'un profilage ou des preuves l'ont montré nécessaire.

Est-il correct de dire que partout où la récursivité est utilisée, une boucle for pourrait être utilisée?

Oui, car la récursivité dans la plupart des processeurs est modélisée avec des boucles et une structure de données de pile.

Et si la récursivité est généralement plus lente, quelle est la raison technique de son utilisation?

Ce n'est pas "généralement plus lent": c'est la récursivité qui n'est pas appliquée correctement qui est plus lente. En plus de cela, les compilateurs modernes sont bons pour convertir certaines récursions en boucles sans même demander.

Et s'il est toujours possible de convertir une récursion en une boucle for, y a-t-il une règle de base pour le faire?

Ecrire des programmes itératifs pour les algorithmes mieux compris lorsqu'ils sont expliqués de manière itérative; écrire des programmes récursifs pour les algorithmes mieux expliqués de manière récursive.

Par exemple, la recherche d'arbres binaires, l'exécution d'un tri rapide et l'analyse d'expressions dans de nombreux langages de programmation sont souvent expliquées de manière récursive. Celles-ci sont également mieux codées récursivement. En revanche, le calcul des factorielles et le calcul des nombres de Fibonacci sont beaucoup plus faciles à expliquer en termes d'itérations. Utiliser la récursivité pour eux, c'est comme écraser les mouches avec un marteau: ce n'est pas une bonne idée, même quand le marteau fait un très bon travail ⁺ .

Question:

Et si la récursivité est généralement plus lente, quelle est la raison technique de son utilisation pour l'itération de boucle?

Répondre :

Parce que dans certains algorithmes, il est difficile de le résoudre de manière itérative. Essayez de résoudre la recherche en profondeur d'abord de manière récursive et itérative. Vous aurez l'idée qu'il est tout simplement difficile de résoudre DFS avec l'itération.

Une autre bonne chose à essayer: essayez d'écrire le tri de fusion de manière itérative. Cela vous prendra un certain temps.

Question:

Est-il correct de dire que partout où la récursivité est utilisée, une boucle for pourrait être utilisée?

Répondre :

Oui. Ce fil a une très bonne réponse pour cela.

Question:

Et s'il est toujours possible de convertir une récursion en une boucle for, y a-t-il une règle de base pour le faire?

Répondre :

Croyez-moi. Essayez d'écrire votre propre version pour résoudre de manière itérative la recherche en profondeur d'abord. Vous remarquerez que certains problèmes sont plus faciles à résoudre de manière récursive.

Astuce: La récursivité est bonne lorsque vous résolvez un problème qui peut être résolu par la technique de division et de conquête .

En plus d'être plus lente, la récursivité peut également entraîner des erreurs de débordement de pile en fonction de sa profondeur.

Pour écrire une méthode équivalente en utilisant l'itération, nous devons explicitement utiliser une pile. Le fait que la version itérative nécessite une pile pour sa solution indique que le problème est suffisamment difficile pour pouvoir bénéficier de la récursivité. En règle générale, la récursivité est la plus appropriée pour les problèmes qui ne peuvent pas être résolus avec une quantité fixe de mémoire et qui nécessitent par conséquent une pile lorsqu'ils sont résolus de manière itérative. Cela dit, la récursivité et l'itération peuvent montrer le même résultat tout en suivant un modèle différent. Pour décider quelle méthode fonctionne le mieux est au cas par cas et la meilleure pratique consiste à choisir en fonction du modèle suivi par le problème.

Par exemple, pour trouver le nième nombre triangulaire de séquence triangulaire: 1 3 6 10 15… Un programme qui utilise un algorithme itératif pour trouver le nième nombre triangulaire:

En utilisant un algorithme itératif:

//Triangular.java
import java.util.*;
class Triangular {
   public static int iterativeTriangular(int n) {
      int sum = 0;
      for (int i = 1; i <= n; i ++)
         sum += i;
      return sum;
   }
   public static void main(String args[]) {
      Scanner stdin = new Scanner(System.in);
      System.out.print("Please enter a number: ");
      int n = stdin.nextInt();
      System.out.println("The " + n + "-th triangular number is: " + 
                            iterativeTriangular(n));
   }
}//enter code here

En utilisant un algorithme récursif:

//Triangular.java
import java.util.*;
class Triangular {
   public static int recursiveTriangular(int n) {
      if (n == 1)
     return 1;  
      return recursiveTriangular(n-1) + n; 
   }

   public static void main(String args[]) {
      Scanner stdin = new Scanner(System.in);
      System.out.print("Please enter a number: ");
      int n = stdin.nextInt();
      System.out.println("The " + n + "-th triangular number is: " + 
                             recursiveTriangular(n)); 
   }
}

La plupart des réponses semblent supposer que iterative= for loop. Si votre boucle for est illimitée ( à la C, vous pouvez faire ce que vous voulez avec votre compteur de boucle), alors c'est correct. S'il s'agit d'une vraie for boucle (par exemple en Python ou dans la plupart des langages fonctionnels où vous ne pouvez pas modifier manuellement le compteur de boucles), alors ce n'est pas correct.

Toutes les fonctions (calculables) peuvent être implémentées à la fois de manière récursive et en utilisant des whileboucles (ou des sauts conditionnels, qui sont fondamentalement la même chose). Si vous vous limitez vraiment à for loops, vous n'obtiendrez qu'un sous-ensemble de ces fonctions (les primitives récursives, si vos opérations élémentaires sont raisonnables). Certes, c'est un sous-ensemble assez important qui contient toutes les fonctions que vous êtes susceptible de rencontrer dans la pratique.

Ce qui est beaucoup plus important, c'est que beaucoup de fonctions sont très faciles à implémenter de manière récursive et terriblement difficiles à implémenter de manière itérative (la gestion manuelle de votre pile d'appels ne compte pas).

Oui, comme dit par Thanakron Tandavas ,

La récursivité est bonne lorsque vous résolvez un problème qui peut être résolu par la technique de division et de conquête.

Par exemple: les tours de Hanoi

1. N anneaux de taille croissante
2. 3 pôles
3. Les anneaux commencent empilés sur le pôle 1. Le but est de déplacer les anneaux pour qu'ils soient empilés sur le pôle 3 ... Mais
   • Ne peut déplacer qu'un anneau à la fois.
   • Impossible de mettre une bague plus grande sur une bague plus petite.
4. La solution itérative est «puissante mais laide»; la solution récursive est «élégante».

Il me semble me souvenir que mon professeur d'informatique disait à l'époque que tous les problèmes qui ont des solutions récursives ont aussi des solutions itératives. Il dit qu'une solution récursive est généralement plus lente, mais elles sont fréquemment utilisées lorsqu'elles sont plus faciles à raisonner et à coder que les solutions itératives.

Cependant, dans le cas de solutions récursives plus avancées, je ne pense pas qu'il sera toujours en mesure de les implémenter en utilisant une simple forboucle.

récursion + mémorisation pourrait conduire à une solution plus efficace par rapport à une approche itérative pure, par exemple vérifier ceci: http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n

Réponse courte: le compromis est que la récursivité est plus rapide et que les boucles for prennent moins de mémoire dans presque tous les cas. Cependant, il existe généralement des moyens de modifier la boucle for ou la récursivité pour la rendre plus rapide