récursivité contre itération

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

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

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

    Certaines optimisations, telles que l’ optimisation des appels de queue , permettent des récurrences plus rapides mais pas toujours possibles, et ne sont pas implémentées dans toutes les langues.

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

    • que c’est plus intuitif dans de nombreux cas quand il imite notre approche du problème
    • que certaines structures de données telles que les arbres sont plus faciles à explorer en utilisant la récursivité (ou nécessiteraient des stacks dans tous les cas)

    Bien sûr, chaque récursion peut être modélisée comme une sorte de boucle: c’est ce que le processeur fera finalement. Et la récursion elle-même, plus directement, consiste à placer les appels de fonction et les étendues dans une stack. Mais transformer votre algorithme récursif en un algorithme en boucle pourrait nécessiter beaucoup de travail et rendre votre code moins maintenable: comme pour toute optimisation, il ne devrait être tenté que lorsqu’un profilage ou des preuves le montrent 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 stack.

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

    Et s’il est toujours possible de convertir une récursion en une boucle for, y a-t-il une méthode empirique 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 binarys, l’exécution de quicksort et l’parsing d’expressions dans de nombreux langages de programmation sont souvent expliquées de manière récursive. Celles-ci sont mieux codées de manière récursive. Par contre, 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 voler des mouches avec une masse: ce n’est pas une bonne idée, même si le marteau fait très bien son travail.


    + J’ai emprunté l’analogie avec le sledgehammer de “Discipline of Programming” de Dijkstra.

    Question:

    Et si la récursivité est généralement plus lente, quelle est la raison technique de l’utiliser 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 difficile de résoudre le problème avec l’itération.

    Une autre bonne chose à essayer: Essayez d’écrire Merge par sorting itératif. Cela vous prendra pas mal de 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 à cela.

    Question:

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

    Répondre :

    Croyez-moi. Essayez d’écrire votre propre version pour résoudre la recherche en profondeur d’abord. Vous remarquerez que certains problèmes sont plus faciles à résoudre récursivement.

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

    En plus d’être plus lente, la récursion peut également entraîner des erreurs de débordement de stack en fonction de la profondeur.

    Pour écrire une méthode équivalente en utilisant une itération, nous devons utiliser explicitement une stack. Le fait que la version itérative nécessite une stack pour sa solution indique que le problème est suffisamment difficile pour qu’il bénéficie d’une 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é de mémoire fixe et requièrent par conséquent une stack lors de la résolution itérative. Cela dit, la récursivité et l’itération peuvent donner le même résultat lorsqu’elles suivent un schéma différent. Pour décider quelle méthode fonctionne le mieux, il est préférable de choisir en fonction du modèle suivi.

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

    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(Ssortingng args[]) { Scanner stdin = new Scanner(System.in); System.out.print("Please enter a number: "); int n = stdin.nextInt(); System.out.println("The " + n + "-th sortingangular 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 boucles), alors c’est correct. Si c’est un réel 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 de manière récursive et en utilisant des boucles while (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 fonctions récursives primitives, si vos opérations élémentaires sont raisonnables). Certes, il s’agit d’un sous-ensemble assez vaste 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 extrêmement difficile à mettre en œuvre de manière itérative (gérer manuellement votre stack d’appels ne compte pas).

    Je crois me souvenir que mon professeur d’informatique disait à l’époque que tous les problèmes comportant des solutions récursives avaient également 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 capable de les implémenter en utilisant une simple boucle.

    Oui, comme dit Thanakron Tandavas ,

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

    Par exemple: Tours de Hanoi

    1. N anneaux en taille croissante
    2. 3 pôles
    3. Les anneaux commencent empilés sur le poteau 1. Le but est de déplacer les anneaux de manière à ce qu’ils soient empilés sur le poteau 3 … Mais
      • Ne peut déplacer qu’un anneau à la fois.
      • Ne peut pas mettre plus grand anneau sur le plus petit.
    4. La solution itérative est «puissante mais laide»; la solution récursive est «élégante».

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

    Réponse courte: la récursion est plus rapide et les boucles 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