Recursion vs boucles

si le rendement est important, alors évaluez les deux et choisissez sur une base rationnelle. Si ce n'est pas le cas, choisissez en fonction de la complexité, en tenant compte de la possibilité d'un débordement de la pile.

Il y a une ligne directrice de la livre classique les éléments du Style de programmation (par Kernighan et Plauger) cet algorithme devrait suivre la structure des données. C'est-à-dire que les structures récursives sont souvent traitées plus clairement avec des algorithmes récursifs.

la Récursivité est utilisé pour exprimer un algorithme qui est naturellement récursive dans une forme qui est plus facilement compréhensible. Un algorithme" naturellement récursif " est un algorithme où la réponse est construite à partir des réponses à des sous-problèmes plus petits qui sont à leur tour construits à partir des réponses à des sous-problèmes encore plus petits, etc. Par exemple, l'informatique factorielle.

Dans un langage de programmation qui n'est pas fonctionnelle, une approche itérative est presque toujours plus rapide et plus efficace qu'un appel récursif approche, donc, la raison d'utiliser la récursivité est la clarté, pas de vitesse. Si une implémentation récursive finit par être moins clair qu'une mise en œuvre itérative, alors par tous les moyens l'éviter.

dans ce cas précis, je jugerais que la mise en œuvre itérative est plus claire.

si vous utilisez un langage fonctionnel (ne semble pas l'être), Utilisez la récursion. Si non, la boucle sera probablement mieux compris par quelqu'un d'autre travaillant sur le projet. Bien sûr, certaines tâches (comme la recherche récursive d'un répertoire) sont mieux adaptées à la récursion que d'autres.

de plus, si le code ne peut pas être optimisé pour la récursion de l'extrémité de la queue, la boucle est plus sûre.

utilisez la boucle. Il est plus facile à lire et à comprendre (lire le code est toujours beaucoup plus difficile que de l'écrire), et il est généralement beaucoup plus rapide.

je préfère les boucles

• la Récursivité est sujette à erreur
• tout le code reste dans une fonction / méthode
• Mémoire et de la vitesse d'épargne

j'utilise stacks (LIFO schema) pour faire fonctionner les boucles

en java, stacks est couvert de Deque interface

// Get all the writable folders under one folder
// java-like pseudocode
void searchWritableDirs(Folder rootFolder){
    List<Folder> response = new List<Folder>(); // Results
    Deque<Folder> folderDeque = new Deque<Folder>(); // Stack with elements to inspect
    folderDeque.add(rootFolder);
    while( ! folderDeque.isEmpty()){
        Folder actual = folder.pop(); // Get last element
        if (actual.isWritable()) response.add(actual); // Add to response
        for(Folder actualSubfolder: actual.getSubFolder()) { 
            // Here we iterate subfolders, with this recursion is not needed
            folderDeque.push(actualSubfolder);
        } 
    } 
    log("Folders " + response.size());
 }

Moins compliqué, plus compact que

// Get all the writable folders under one folder
// java-like pseudocode
void searchWritableDirs(Folder rootFolder){
    List<Folder> response = new List<Folder>(); // Results
    rec_searchWritableDirs(actualSubFolder,response);
    log("Folders " + response.size());
}

private void rec_searchWritableDirs(Folder actual,List<Folder> response) {
   if (actual.isWritable()) response.add(actual); // Add to response
   for(Folder actualSubfolder: actual.getSubFolder()) {
       // Here we iterate subfolders, recursion is needed
       rec_searchWritableDirs(actualSubFolder,response);
   }                
}

ce dernier a moins de code, mais deux fonctions et il est plus difficile de comprendre le code, À mon humble avis.

je dirais que la récursivité version est mieux compréhensible, mais seulement avec les commentaires:

Item Search(string desired, Scope scope) {
    // search local items
    foreach(Item item in scope.items)
        if(item.name == desired)
            return item;

    // also search parent
    return scope.Parent ? Search(desired, scope.Parent) : null;
}

Il est beaucoup plus facile d'expliquer cette version. Essayez d'écrire un joli commentaire sur la version loop et vous verrez.

il est prouvé que tous les algorithmes de récursion de la queue peuvent être déroulés en boucle, et vice versa. D'une manière générale, une implémentation récursive d'un algorithme récursif est plus claire à suivre pour le programmeur que l'implémentation de boucle, et est également plus facile à déboguer. De façon générale, la performance réelle de l'implémentation de la boucle sera plus rapide, car une branche/saut dans une boucle est généralement plus rapide à exécuter que de pousser et de faire sauter un cadre de pile.

Personnellement en ce qui concerne les algorithmes recursifs de queue, je préfère m'en tenir à l'implémentation recursive dans toutes les situations sauf les plus exigeantes en termes de performances.

je trouve la récursion plus naturelle, mais vous pourriez être forcé d'utiliser la boucle si votre compilateur ne fait pas l'optimisation des appels de queue et que votre arborescence/liste est trop profonde pour la taille de la pile.

je préfère habituellement l'utilisation de boucles. La plupart des bonnes conceptions OOP vous permettront d'utiliser des boucles sans avoir à utiliser la récursion (et donc d'empêcher le programme de pousser tous ces paramètres et adresses désagréables à la pile).

Il a plus d'une utilisation dans le code de procédure, où il semble plus logique de penser de manière récursive (en raison du fait que vous ne pouvez pas facilement état de stockage ou méta-données (information?) et ainsi vous créez plus de situations qui mériteraient utiliser.)

la récursion est bonne pour proto-taper une fonction et / ou écrire une base, mais une fois que vous savez que le code fonctionne et que vous y retournez pendant la phase d'optimisation, essayez de le remplacer par une boucle.

encore une fois, tout cela est opiniâtre. Va avec ce qui marche le mieux pour toi.

si votre code est compilé, cela fera probablement peu de différence. Faites quelques tests et voyez combien de mémoire est utilisée et à quelle vitesse elle tourne.

si le système sur lequel vous travaillez a une petite pile (Systèmes Intégrés), la profondeur de récursion serait limitée, donc le choix de l'algorithme basé sur la boucle serait souhaitable.

Vous pouvez aussi écrire la boucle dans un format plus lisible. C for(init;while;increment) ont quelques inconvénients de lisibilité depuis le increment commande est mentionné au début, mais exécuté à la fin de la boucle.

VOS DEUX ÉCHANTILLONS NE SONT PAS ÉQUIVALENTS. Le récursive exemple échoue et la boucle ne sera pas, si vous l'appelez comme: Search(null,null). Cela rend la version loop meilleure pour moi.

Voici les échantillons modifiés (et en supposant nul est false)

la Récursivité (fixe et la queue de l'appel optimisable)

Item Search(string desired, Scope scope) {

    if (!scope) return null

    foreach(Item item in scope.items)
        if(item.name == desired)
            return item;

    //search parent (recursive)
    return Search(desired, scope.Parent);
}

Boucle

Item Search(string desired, Scope scope) {
    // start
    Scope cur = scope;

    while(cur) {
        foreach(Item item in cur.items)
            if(item.name == desired)
                return item;

        //search parent
        cur = cur.Parent;

    } //loop

    return null;
}

Eh bien j'ai vu des tonnes de réponses et j'ai même accepté la réponse mais je n'ai jamais vu la bonne et je me demandais pourquoi...

pour faire court:

toujours éviter les récursions si vous pouvez faire la même unité pour être produite par des boucles!

comment fonctionne la récursion?

• le cadre dans la mémoire de pile est alloué pour un appel de fonction unique

• le cadre contient une référence au méthode

* si la méthode a des objets, les objets sont placés dans la mémoire tas et Frame contiendra des références à ces objets dans la mémoire tas.

•ces étapes sont effectuées pour chaque appel de méthode!

Risques :

• StackOverFlow quand la pile n'a pas de mémoire pour mettre de nouvelles méthodes récursives.

* OutOfMemory quand le tas n'a pas de mémoire pour mettre des objets stockés récursifs.

Comment boucle de travail?

* toutes les étapes précédentes, sauf que l'exécution de code répété à l'intérieur de la boucle ne consommera pas d'autres données si déjà consommées.

Risques :

• un seul risque est à l'intérieur de la boucle while lorsque votre condition n'existera jamais... Eh bien, qui ne causera pas de crash ou autre chose, il ne sera tout simplement pas quitter la boucle si vous faites naïvement while(true) :)

Test:

Faire en votre logiciel:

private Integer someFunction(){

return someFunction();
}

Vous obtiendrez StackOverFlow exception dans une seconde et peut-être OutOfMemory trop

la deuxième:

while(true){

}

Le logiciel seulement le gel et pas de plantage qui va se passer:

Dernier point mais non le moindre - for boucles :

Toujours aller avec for boucles parce que ceci ou cela cette boucle vous force quelque peu à donner le point de rupture au-delà duquel la boucle ne va pas, sûrement vous pouvez être super en colère et juste trouver un moyen de faire for boucle ne s'arrête jamais mais je vous conseille d'utiliser toujours des boucles au lieu de la récursion pour la gestion de la mémoire et une meilleure productivité pour votre logiciel qui est un énorme problème de nos jours.

Références:

allocation de mémoire basée sur la pile

éviter la récursion. Il y a des Chances que ce morceau de code devra être maintenu à un moment donné et ce sera plus facile s'il n'est pas fait avec récursion. Deuxièmement, le temps d'exécution sera plus lent.