récursion contre itération

Question

Est-il correct de dire que partout où la récursion est utilisée une for boucle pourrait être utilisée ? Et si la récursion est généralement plus lente, quelle est la raison technique pour ne jamais l'utiliser au lieu de la boucle ? for itération de la boucle ?

Et s'il est toujours possible de convertir une récursion en une for loop existe-t-il une méthode empirique pour le faire ?

Answer 1

La récursion 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 mettre en œuvre l'isolation de la portée.

Certaines optimisations, comme optimisation des appels de queue rendent les récursions plus rapides, mais ne sont pas toujours possibles et ne sont pas implémentées dans tous les langages.

Les principales raisons d'utiliser la récursion sont

• qu'il est plus intuitif dans de nombreux cas quand il imite notre approche du problème.
• que certaines structures de données, comme les arbres, sont plus faciles à explorer en utilisant la récursion (ou auraient de toute façon besoin de piles)

Bien sûr, toute récursion peut être modélisé comme une sorte de boucle : c'est ce que fera finalement le CPU. Et la récursion elle-même, plus directement, signifie mettre 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 facile à maintenir : comme pour toute optimisation, elle ne devrait être tentée que si un profilage ou des preuves montrent qu'elle est nécessaire.

Answer 2

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

Oui, car la récursion dans la plupart des CPU est modélisée par des boucles et une structure de données de type pile.

Et si la récursion est généralement plus lente, quelle est la raison technique pour l'utiliser ?

Ce n'est pas "habituellement plus lent" : c'est la récursion appliquée de manière incorrecte qui est plus lente. De plus, les compilateurs modernes sont capables de convertir certaines récursions en boucles sans même le demander.

Et s'il est toujours possible de convertir une récursion en une boucle for, existe-t-il une méthode empirique pour le faire ?

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

Par exemple, la recherche d'arbres binaires, l'exécution de quicksort et l'analyse d'expressions dans de nombreux langages de programmation sont souvent expliquées de manière récursive. Il est également préférable de les coder de manière récursive. En revanche, le calcul des factorielles et des nombres de Fibonacci est beaucoup plus facile à expliquer en termes d'itérations. Utiliser la récursivité pour ces calculs, c'est comme écraser des mouches avec un marteau de forgeron : ce n'est pas une bonne idée, même si le marteau de forgeron fait un très bon travail + .

---

+ J'ai emprunté l'analogie du marteau de forgeron à la "Discipline de la programmation" de Dijkstra.

Answer 3

Question :

Et si la récursion est généralement plus lente, quelle est la raison technique de l'utiliser plutôt que l'itération de la boucle for ?

Réponse :

Parce que dans certains algorithmes, il est difficile de les résoudre de manière itérative. Essayez de résoudre la recherche en profondeur à la fois récursivement et itérativement. Vous vous rendrez compte qu'il est très difficile de résoudre la DFS par itération.

Une autre bonne chose à essayer : Essayez d'écrire Merge sort de manière itérative. Cela vous prendra pas mal de temps.

Question :

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

Réponse :

Oui. Ceci filetage a une très bonne réponse à cette question.

Question :

Et s'il est toujours possible de convertir une récursion en une boucle for, existe-t-il une méthode empirique pour le faire ?

Réponse :

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

_Conseil : La récursion est bonne lorsque vous résolvez un problème qui peut être résolu par diviser pour mieux régner technique._

Answer 4

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

Answer 5

Pour écrire une méthode équivalente 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 qu'il puisse bénéficier de la récursion. En règle générale, la récursion est plus adaptée aux problèmes qui ne peuvent pas être résolus avec une quantité fixe de mémoire et qui, par conséquent, nécessitent une pile lorsqu'ils sont résolus de manière itérative. Cela dit, la récursion et l'itération peuvent donner le même résultat alors qu'elles suivent un modèle différent. Pour décider quelle méthode fonctionne le mieux, il faut procéder au cas par cas et la meilleure pratique consiste à choisir en fonction du modèle que suit le problème.

Par exemple, pour trouver le nième nombre triangulaire de Suite 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)); 
   }
}