Pourquoi préférer la récursion à l'itération?

essayez de mettre en œuvre depth-première recherche récursive et itérative et dites-moi laquelle vous a donné un temps plus facile de celui-ci. Ou de fusion de tri. Pour beaucoup de problèmes, il s'agit de maintenir explicitement votre propre pile par opposition à laisser vos données sur la pile de fonction.

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 parce que l'itération implique un état mutable (l'indice).

comme d'autres l'ont dit, il n'y a rien d'intrinsèquement moins performant dans la récursion. Il y a des langues où il sera plus lent, mais ce n'est pas une règle universelle.

cela dit, pour moi la récursion est un outil, à utiliser quand ça a du sens. Il y a des algorithmes qui sont mieux représentés sous forme de récursion (tout comme certains sont mieux représentés par itération).

Affaire au point:

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

Je ne peux pas imaginer solution itérative qui pourrait éventuellement l'intention plus claire que ça.

voici quelques informations sur les avantages et les inconvénients de la récursion et de l'itération en c:

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

la plupart du temps pour moi, la récursion est parfois plus facile à comprendre que l'itération.

itération est juste une forme spéciale de récursion.

plusieurs choses:

1. itération n'est pas nécessairement plus rapide
2. racine de tout mal: encourager quelque chose juste parce qu'il pourrait être modérément plus rapide est prématuré; il y a d'autres considérations.
3. Récursivité souvent beaucoup plus succinctement et de communiquer clairement votre intention
4. en évitant l'état mutable en général, les langages de programmation fonctionnels sont plus faciles à raisonner et à déboguer, et la récursion en est un exemple.
5. la récursion prend plus de mémoire que l'itération.

la récursion est l'une de ces choses qui semblent élégantes ou efficaces en théorie mais en pratique est généralement moins efficace (à moins que le compilateur ou le recompilateur dynamique) est en train de changer ce que fait le code. En général, tout ce qui provoque des appels de sous-programmes inutiles sera plus lent, surtout lorsque plus d'un argument est poussé/déclenché. Tout ce que vous pouvez faire pour supprimer les cycles de processeur, c'est-à-dire les instructions que le processeur doit mâcher, est juste. Les compilateurs peuvent faire un bon travail de ce ces jours en général, mais il est toujours bon de savoir comment écrire du code efficace en main.

Je ne pense pas qu'il y ait quelque chose d'intrinsèquement moins performant dans la récursion - du moins dans l'abstrait. La récursion est une forme spéciale d'itération. Si un langage est conçu pour bien supporter la récursion, il est possible qu'il puisse fonctionner aussi bien que l'itération.

en général, la récursion rend explicite l'état que vous avancez dans la prochaine itération (ce sont les paramètres). Cela peut rendre plus facile pour les processeurs de langue de paralléliser exécution. 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, il a tendance à être dans l'autre sens. Je pense que cela vaut en général pour les langues compilées de façon adaptative par rapport aux langues compilées à l'avance.

Edit: Par "en général", je veux dire quelque chose comme un 60/40. Cela dépend beaucoup de l'efficacité avec laquelle le langage traite les appels de méthodes. Je pense que la compilation JIT favorise la récursion parce qu'elle peut choisir comment gérer l'incrustation et utiliser runtime données en optimisation. Cela dépend beaucoup de l'algorithme et du compilateur en question. Java en particulier continue de devenir plus intelligent pour gérer la récursion.

Quantitative des résultats de l'étude avec Java (lien PDF) . Notez qu'il s'agit principalement d'algorithmes de tri, et qu'ils utilisent une ancienne Machine virtuelle Java (1.5.x si je lis à droite). ils obtiennent parfois une amélioration de performance 2:1 ou 4:1 en utilisant l'implémentation récursive, et la récursion est rarement significativement plus lente. d'après mon expérience personnelle, la différence n'est pas souvent aussi prononcée, mais une amélioration de 50% est fréquente lorsque j'utilise la récursion de façon sensée.

je trouve difficile de raisonner que l'un est meilleur que l'autre tout le temps.

Im travaillant sur une application mobile qui a besoin de faire du travail de fond sur le système de fichiers utilisateur. Un des threads de fond doit balayer l'ensemble du système de fichiers de temps en temps, pour maintenir les données mises à jour à l'utilisateur. Donc, par peur du débordement de la pile , j'avais écrit un algorithme itératif. Aujourd'hui, j'ai écrit une récursive, pour le même travail. À ma surprise, l'algorithme itératif est plus rapide: récursif - >37s, itératif - > 34s (travaillant 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: - profondeur itérative-première recherche, avec rétrotractage 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;
        }

certes, l'itératif n'est pas Élégant, mais bien qu'il soit actuellement mis en œuvre d'une manière inefficace, il est encore plus rapide que l'itératif récursif. Et j'ai un meilleur contrôle sur elle, car je ne veut pas qu'il tourne à pleine vitesse, et laissera le collecteur d'ordures faire son travail plus fréquemment.

de toute façon, je ne vais pas prendre pour acquis qu'une méthode est meilleure que l'autre, et examinera d'autres algorithmes qui sont actuellement récursive. Mais au moins à partir des 2 algorithmes ci-dessus, celui 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 en fait beaucoup de place pour l'optimisation - à savoir un facteur de 43! rien de tout cela n'a quelque chose à voir avec itération vs récursion.

quand une application a été accordée que loin , il arrive au point où les cycles enregistrés par itération contre la récursion pourrait faire une différence.

comme une itération de bas niveau traite avec le registre CX pour compter les boucles, et bien sûr les registres de données. La récursion ne traite pas seulement du fait qu'elle ajoute des références au pointeur de pile pour conserver les références des appels précédents et ensuite comment revenir en arrière.-

mon professeur D'Université m'a dit que quoi que vous fassiez avec la récursion peut être fait avec des itérations et viceversa, cependant parfois est plus simple de le faire par la récursion que L'itération (plus élégant) mais à une performance le niveau est préférable d'utiliser des Itérations.-

la récursion est la mise en œuvre typique de l'itération. C'est juste un niveau inférieur d'abstraction (au 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écursion à un explosif: on peut atteindre un grand résultat en un rien de temps. Mais si vous l'utilisez sans précautions le résultat pourrait être désastreux.

j'ai été très impressionné en prouvant de la complexité pour la récursion qui calcule des nombres de Fibonacci ici . Dans ce cas, la récursion présente une complexité O((3/2)^n) Alors que l'itération n'est que O(n). Le calcul de n = 46 avec la récursion écrite sur c # prend une demi-minute! Wow...

à mon humble avis la récursivité doit être utilisé que si la nature des entités adapté pour la récursivité (arbres, de vérification de syntaxe, de ...) et jamais parce que de l'esthétique. La performance et la consommation de ressources de tout code récursif "divin" doivent être scrutées à la loupe.

"itération plus performante que récursion" est en fait propre au langage et/ou au compilateur. Le cas qui vient à l'esprit est lorsque le compilateur ne boucle-déroulage. Si vous avez mis en œuvre une solution récursive dans ce cas, cela va être un peu plus lent.

c'est là que ça paie d'être un scientifique (tester des hypothèses) et de connaître ses outils...

itération est plus performante que récursion, Non?

Oui.

cependant, quand vous avez 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 itérations vous finirez par réinventer la pile et créer un code moche, comparé à la version recursive élégante du code.

qui dit, itération sera toujours plus rapide que récursion . (dans une Architecture Von Neumann), donc si vous utilisez toujours la récursion, même si une boucle suffit, vous paierez une pénalité de performance.

est-ce que la récursion est plus rapide que la boucle?

sur ntfs UNC max chemin est de 32 ko

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 n'importe quelle méthode récursive, tôt ou tard tout donnera le débordement de pile.

seul un bon code itératif léger doit être utilisé pour numériser les dossiers de manière professionnelle.

croyez ou non, la plupart des antivirus top ne peut pas scanner la profondeur maximale des dossiers UNC.