Pourquoi la récursivité devrait-elle être préférée à l’itération?

L’itération est plus performante que la récursivité, non? Alors pourquoi certaines personnes pensent-elles que la récursivité est meilleure (plus élégante, selon leurs mots) que l’itération? Je ne vois vraiment pas pourquoi certaines langues comme Haskell ne permettent pas l’itération et encouragent la récursivité? N’est-ce pas absurde d’encourager quelque chose qui a de mauvaises performances (et cela aussi quand une option plus performante, à savoir la récursivité est disponible)? S’il vous plaît apporter un peu de lumière à ce sujet. Merci.

L’itération est plus performante que la récursivité, non?

Pas nécessairement. Cette conception provient de nombreux langages de type C, où l’appel d’une fonction, récursive ou non, avait une grande charge et créait une nouvelle stack pour chaque appel.

Pour de nombreux langages, ce n’est pas le cas et la récursivité est également ou plus performante qu’une version itérative. De nos jours, même certains compilateurs C réécrivent certaines constructions récursives dans une version itérative, ou réutilisent le cadre de la stack pour un appel récursif de queue.

Essayez d’implémenter de manière récursive et itérative la recherche en profondeur d’abord et dites-moi laquelle vous a donné le plus de temps. Ou fusionner le sorting. Pour beaucoup de problèmes, il s’agit de maintenir explicitement votre propre stack plutôt que de laisser vos données sur la stack de fonctions.

Je ne peux pas parler à Haskell car je ne l’ai jamais utilisé, mais c’est pour répondre à la partie plus générale de la question posée dans votre titre.

Haskell ne permet pas l’itération car l’itération implique un état mutable (l’index).

Comme d’autres l’ont déclaré, il n’ya rien de moins performant en matière de récursivité. Il y a certaines langues où ce sera plus lent, mais ce n’est pas une règle universelle.

Cela étant dit, pour moi, la récursion est un outil à utiliser lorsque cela a du sens. Certains algorithmes sont mieux représentés sous forme de récursivité (tout comme certains sont meilleurs par itération).

Par exemple:

fib 0 = 0 fib 1 = 1 fib n = fib(n-1) + fib(n-2) 

Je ne peux pas imaginer une solution itérative susceptible de rendre l’intention plus claire que cela.

Voici quelques informations sur les avantages et inconvénients de la récursivité et de l’itération dans c:

http://www.stanford.edu/~blp/writings/clc/recursion-vs-iteration.html

La récursivité est parfois plus facile à comprendre que l’itération.

L’itération n’est qu’une forme de récursivité particulière.

Plusieurs choses:

  1. L’itération n’est pas nécessairement plus rapide
  2. Racine de tous les maux: il est prématuré d’encourager quelque chose simplement parce qu’il pourrait être modérément plus rapide; Il y a d’autres considérations.
  3. La récursivité est souvent beaucoup plus succincte et communique clairement votre intention
  4. En évitant les états mutables en général, les langages de programmation fonctionnels sont plus faciles à raisonner et à déboguer, et la récursivité en est un exemple.
  5. La récursion prend plus de mémoire que l’itération.

La récursivité est une de ces choses qui semblent élégantes ou efficaces en théorie, mais en pratique, elles sont généralement moins efficaces (à moins que le compilateur ou le recompilateur dynamic) ne modifient ce que fait le code. En général, tout ce qui provoque des appels de sous-programmes inutiles sera plus lent, en particulier lorsque plus d’un argument est poussé / sauté. Tout ce que vous pouvez faire pour supprimer les cycles du processeur, c’est-à-dire les instructions que le processeur doit mâcher, est un jeu équitable. Les compilateurs peuvent faire du bon travail ces jours-ci en général, mais il est toujours bon de savoir écrire un code efficace à la main.

Je ne pense pas que la récursivité soit insortingnsèquement moins performante – du moins dans l’abstrait. La récursivité est une forme particulière d’itération. Si un langage est conçu pour prendre en charge correctement la récursivité, il est possible qu’il puisse fonctionner aussi bien que l’itération.

En général, la récursivité rend explicite l’état que vous apportez dans la prochaine itération (ce sont les parameters). Cela peut faciliter l’exécution parallèle des processeurs de langage. Au moins, c’est une direction que les concepteurs de langage essaient d’exploiter.

En Java, les solutions récursives sont généralement plus performantes que les solutions non récursives. En C, c’est l’inverse. Je pense que cela vaut en général pour les langages compilés de manière adaptative et les langages compilés en avance.

Edit: Par “généralement” je veux dire quelque chose comme une division 60/40. Il est très dépendant de l’efficacité avec laquelle le langage gère les appels de méthode. Je pense que la compilation JIT favorise la récursivité car elle permet de choisir comment gérer l’inline et d’utiliser les données d’exécution dans l’optimisation. C’est très dépendant de l’algorithme et du compilateur en question. Java en particulier continue à être plus intelligent sur la gestion de la récursivité.

Résultats de l’étude quantitative avec Java (lien PDF) . Notez que ce sont principalement des algorithmes de sorting et utilisent une ancienne machine virtuelle Java (1.5.x si je lis bien). Ils utilisent parfois une amélioration des performances 2: 1 ou 4: 1 en utilisant l’implémentation récursive, et la récursivité est rarement plus lente. Dans mon expérience personnelle, la différence n’est pas souvent prononcée, mais une amélioration de 50% est courante lorsque j’utilise judicieusement la récursivité.

J’ai du mal à comprendre que l’un est meilleur que l’autre tout le temps.

Je travaille sur une application mobile qui doit faire un travail de fond sur le système de fichiers utilisateur. L’un des threads d’arrière-plan doit balayer de temps en temps l’ensemble du système de fichiers pour conserver les données mises à jour à l’utilisateur. Donc, dans la peur de Stack Overflow, j’avais écrit un algorithme itératif. Aujourd’hui, j’ai écrit un article récursif pour le même travail. À ma grande surprise, l’algorithme itératif est plus rapide: récursif -> 37s, itératif -> 34s (travaillant exactement sur la même structure de fichier).

Récursive:

 private long recursive(File rootFile, long counter) { long duration = 0; sendScanUpdateSignal(rootFile.getAbsolutePath()); if(rootFile.isDirectory()) { File[] files = getChildren(rootFile, MUSIC_FILE_FILTER); for(int i = 0; i < files.length; i++) { duration += recursive(files[i], counter); } if(duration != 0) { dhm.put(rootFile.getAbsolutePath(), duration); updateDurationInUI(rootFile.getAbsolutePath(), duration); } } else if(!rootFile.isDirectory() && checkExtension(rootFile.getAbsolutePath())) { duration = getDuration(rootFile); dhm.put(rootFile.getAbsolutePath(), getDuration(rootFile)); updateDurationInUI(rootFile.getAbsolutePath(), duration); } return counter + duration; } 

Itératif: - recherche itérative en profondeur, avec retour en arrière récursif

 private void traversal(File file) { int pointer = 0; File[] files; boolean hadMusic = false; long parentTimeCounter = 0; while(file != null) { sendScanUpdateSignal(file.getAbsolutePath()); try { Thread.sleep(Constants.THREADS_SLEEP_CONSTANTS.TRAVERSAL); } catch (InterruptedException e) { e.printStackTrace(); } files = getChildren(file, MUSIC_FILE_FILTER); if(!file.isDirectory() && checkExtension(file.getAbsolutePath())) { hadMusic = true; long duration = getDuration(file); parentTimeCounter = parentTimeCounter + duration; dhm.put(file.getAbsolutePath(), duration); updateDurationInUI(file.getAbsolutePath(), duration); } if(files != null && pointer < files.length) { file = getChildren(file,MUSIC_FILE_FILTER)[pointer]; } else if(files != null && pointer+1 < files.length) { file = files[pointer+1]; pointer++; } else { pointer=0; file = getNextSybling(file, hadMusic, parentTimeCounter); hadMusic = false; parentTimeCounter = 0; } } } private File getNextSybling(File file, boolean hadMusic, long timeCounter) { File result= null; //se o file é /mnt, para if(file.getAbsolutePath().compareTo(userSDBasePointer.getParentFile().getAbsolutePath()) == 0) { return result; } File parent = file.getParentFile(); long parentDuration = 0; if(hadMusic) { if(dhm.containsKey(parent.getAbsolutePath())) { long savedValue = dhm.get(parent.getAbsolutePath()); parentDuration = savedValue + timeCounter; } else { parentDuration = timeCounter; } dhm.put(parent.getAbsolutePath(), parentDuration); updateDurationInUI(parent.getAbsolutePath(), parentDuration); } //procura irmao seguinte File[] syblings = getChildren(parent,MUSIC_FILE_FILTER); for(int i = 0; i < syblings.length; i++) { if(syblings[i].getAbsolutePath().compareTo(file.getAbsolutePath())==0) { if(i+1 < syblings.length) { result = syblings[i+1]; } break; } } //backtracking - adiciona pai, se tiver filhos musica if(result == null) { result = getNextSybling(parent, hadMusic, parentDuration); } return result; } 

Bien sûr, l'itératif n'est pas élégant, mais bien qu'il soit actuellement implémenté de manière inefficace, il est toujours plus rapide que celui qui est récursif. Et je le contrôle mieux, car je ne veux pas qu'il fonctionne à plein régime, et permettra au ramasse-miettes de faire son travail plus fréquemment.

Quoi qu’il en soit, je ne tiendrai pas pour acquis qu’une méthode est meilleure que l’autre, et passera en revue les autres algorithmes actuellement récursifs. Mais au moins des 2 algorithmes ci-dessus, l’itératif sera celui du produit final.

Je pense que cela aiderait à comprendre ce qu’est vraiment la performance. Ce lien montre comment une application parfaitement codée a beaucoup de place pour l’optimisation – à savoir un facteur de 43! Rien de tout cela n’avait à voir avec l’itération ou la récursivité.

Lorsqu’une application a été mise au point jusque là, les cycles enregistrés par itération et contre la récursivité peuvent réellement faire la différence.

En tant que bas niveau ITERATION traite du registre CX pour compter les boucles et, bien sûr, des registres de données. La RECURSION ne traite pas seulement de cela, elle ajoute également des références au pointeur de la stack pour conserver les références des appels précédents et ensuite comment revenir en arrière.

Mon professeur universitaire m’a dit que tout ce que vous faites avec la récursivité peut être fait avec les itérations et vice-versa, mais il est parfois plus simple de le faire par récursivité que par itération (plus élégante) mais il est préférable d’utiliser des itérations.

La récursivité est l’implémentation typique de l’itération. C’est juste un niveau d’abstraction inférieur (du moins en Python):

 class iterator(object): def __init__(self, max): self.count = 0 self.max = max def __iter__(self): return self # I believe this changes to __next__ in Python 3000 def next(self): if self.count == self.max: raise StopIteration else: self.count += 1 return self.count - 1 # At this level, iteration is the name of the game, but # in the implementation, recursion is clearly what's happening. for i in iterator(50): print(i) 

Je comparerais la récursivité avec un explosif: vous pouvez atteindre un grand résultat en un rien de temps. Mais si vous l’utilisez sans préavis, le résultat pourrait être désastreux.

J’ai été très impressionné en prouvant la complexité de la récursivité qui calcule ici les nombres de Fibonacci. La récursivité dans ce cas a la complexité O ((3/2) ^ n) alors que l’itération est juste O (n). Le calcul de n = 46 avec la récursivité écrite sur c # prend une demi-minute! Sensationnel…

La récursivité IMHO ne devrait être utilisée que si la nature des entités convient bien à la récursivité (arborescences, parsing syntaxique,…) et jamais à des fins esthétiques. Les performances et la consommation de ressources de tout code récursif “divin” doivent être examinées.

“L’itération est plus performante que la récursivité” est vraiment spécifique au compilateur et / ou au langage. Le cas qui me vient à l’esprit est lorsque le compilateur effectue un déroulement en boucle. Si vous avez implémenté une solution récursive dans ce cas, cela va être un peu plus lent.

C’est là que ça paye d’être un scientifique (tester des hypothèses) et de connaître vos outils …

L’itération est plus performante que la récursivité, non?

Oui.

Cependant, lorsque vous rencontrez un problème qui correspond parfaitement à une structure de données récursive, la meilleure solution est toujours récursive .

Si vous prétendez résoudre le problème avec des itérations, vous finirez par réinventer la stack et créer un code plus désordonné et plus laid, comparé à la version récursive élégante du code.

Cela dit, l’ itération sera toujours plus rapide que la récursivité . (dans une architecture Von Neumann), donc si vous utilisez toujours la récursivité, même si une boucle suffit, vous payez une pénalité de performance.

La récursivité est-elle plus rapide que la boucle?

sur ntfs UNC max path comme 32K
C: \ A \ B \ X \ C …. plus de 16K dossiers peuvent être créés …

Mais vous ne pouvez même pas compter le nombre de dossiers avec une méthode récursive, tôt ou tard, tous donneront un débordement de stack.

Seul un code itératif Good Good doit être utilisé pour parsingr les dossiers de manière professionnelle.

Croyez ou non, la plupart des principaux antivirus ne peuvent pas parsingr la profondeur maximale des dossiers UNC.