Y a-t-il un impact sur les performances si nous utilisons une boucle au lieu de la récursivité ou vice versa dans les algorithmes où les deux peuvent servir le même objectif? Par exemple: Vérifiez si la chaîne donnée est un palindrome. J'ai vu de nombreux programmeurs utiliser la récursivité comme moyen de montrer quand un algorithme d'itération simple peut convenir. Le compilateur joue-t-il un rôle essentiel pour décider quoi utiliser?

Il est possible que la récursivité soit plus coûteuse, selon que la fonction récursive est récursive de queue (la dernière ligne est un appel récursif). La récursivité de queue doit être reconnue par le compilateur et optimisée par rapport à son homologue itérative (tout en conservant l'implémentation concise et claire que vous avez dans votre code).

J'écrirais l'algorithme de la manière la plus logique et la plus claire pour le pauvre suceur (que ce soit vous-même ou quelqu'un d'autre) qui doit maintenir le code dans quelques mois ou quelques années. Si vous rencontrez des problèmes de performances, profilez votre code, puis examinez l'optimisation en passant à une implémentation itérative. Vous voudrez peut-être examiner la mémorisation et la programmation dynamique .

Les boucles peuvent obtenir un gain de performances pour votre programme. La récursivité peut obtenir un gain de performances pour votre programmeur. Choisissez ce qui est le plus important dans votre situation!

Comparer la récursivité à l'itération revient à comparer un tournevis cruciforme à un tournevis à tête plate. Pour la plupart, vous pouvez retirer toute vis à tête cruciforme à tête plate, mais ce serait plus facile si vous utilisiez le tournevis conçu pour cette vis, n'est-ce pas?

Certains algorithmes se prêtent simplement à la récursivité en raison de leur conception (séquences de Fibonacci, traversée d'une structure arborescente, etc.). La récursivité rend l'algorithme plus succinct et plus facile à comprendre (donc partageable et réutilisable).

De plus, certains algorithmes récursifs utilisent "l'évaluation paresseuse", ce qui les rend plus efficaces que leurs frères itératifs. Cela signifie qu'ils ne font les calculs coûteux qu'au moment où ils sont nécessaires plutôt qu'à chaque exécution de la boucle.

Cela devrait suffire pour vous aider à démarrer. Je trouverai aussi des articles et des exemples pour vous.

Lien 1: Haskel vs PHP (récursion vs itération)

Voici un exemple où le programmeur a dû traiter un grand ensemble de données en utilisant PHP. Il montre à quel point cela aurait été facile à gérer dans Haskel en utilisant la récursivité, mais comme PHP n'avait pas de moyen facile d'accomplir la même méthode, il a été forcé d'utiliser l'itération pour obtenir le résultat.

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

Lien 2: Maîtriser la récursivité

La mauvaise réputation de la récursivité vient principalement des coûts élevés et de l'inefficacité des langues impératives. L'auteur de cet article explique comment optimiser les algorithmes récursifs pour les rendre plus rapides et plus efficaces. Il explique également comment convertir une boucle traditionnelle en une fonction récursive et les avantages de l'utilisation de la récursivité d'extrémité. Ses derniers mots résument vraiment certains de mes points clés, je pense:

"La programmation récursive donne au programmeur une meilleure façon d'organiser le code d'une manière qui soit à la fois maintenable et logique."

https://developer.ibm.com/articles/l-recurs/

Lien 3: la récursivité est-elle toujours plus rapide que la boucle? (Répondre)

Voici un lien vers une réponse à une question de stackoverflow similaire à la vôtre. L'auteur souligne que de nombreux points de repère associés à la récurrence ou à la boucle sont très spécifiques au langage. Les langages impératifs sont généralement plus rapides en utilisant une boucle et plus lents avec la récursivité et vice-versa pour les langages fonctionnels. Je suppose que le principal point à retenir de ce lien est qu'il est très difficile de répondre à la question dans un sens de langue agnostique / situation aveugle.

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

La récursivité est plus coûteuse en mémoire, car chaque appel récursif nécessite généralement de pousser une adresse mémoire vers la pile - pour que plus tard le programme puisse revenir à ce point.

Pourtant, il existe de nombreux cas dans lesquels la récursivité est beaucoup plus naturelle et lisible que les boucles - comme lorsque vous travaillez avec des arbres. Dans ces cas, je recommanderais de s'en tenir à la récursivité.

En règle générale, on s'attendrait à ce que la pénalité de performance se situe dans l'autre sens. Les appels récursifs peuvent conduire à la construction de cadres de pile supplémentaires; la pénalité pour cela varie. De plus, dans certains langages comme Python (plus correctement, dans certaines implémentations de certains langages ...), vous pouvez exécuter des limites de pile assez facilement pour des tâches que vous pourriez spécifier récursivement, comme trouver la valeur maximale dans une structure de données arborescente. Dans ces cas, vous voulez vraiment vous en tenir aux boucles.

L'écriture de bonnes fonctions récursives peut réduire quelque peu la pénalité des performances, en supposant que vous disposez d'un compilateur qui optimise les récursions de queue, etc. sur.)

Hormis les cas «marginaux» (calcul haute performance, très grande profondeur de récursivité, etc.), il est préférable d'adopter l'approche qui exprime le plus clairement votre intention, est bien conçue et maintenable. Optimisez uniquement après avoir identifié un besoin.

La récursivité est meilleure que l'itération pour les problèmes qui peuvent être décomposés en plusieurs morceaux plus petits.

Par exemple, pour créer un algorithme de Fibonnaci récursif, vous décomposez fib (n) en fib (n-1) et fib (n-2) et calculez les deux parties. L'itération ne vous permet de répéter une seule fonction encore et encore.

Cependant, Fibonacci est en fait un exemple cassé et je pense que l'itération est en fait plus efficace. Notez que fib (n) = fib (n-1) + fib (n-2) et fib (n-1) = fib (n-2) + fib (n-3). fib (n-1) est calculé deux fois!

Un meilleur exemple est un algorithme récursif pour un arbre. Le problème de l'analyse du nœud parent peut être décomposé en plusieurs problèmes plus petits d'analyse de chaque nœud enfant. Contrairement à l'exemple de Fibonacci, les petits problèmes sont indépendants les uns des autres.

Donc oui - la récursivité est meilleure que l'itération pour les problèmes qui peuvent être décomposés en plusieurs problèmes plus petits, indépendants et similaires.

Vos performances se détériorent lors de l'utilisation de la récursivité, car l'appel d'une méthode, dans n'importe quelle langue, implique beaucoup de préparation: le code appelant publie une adresse de retour, les paramètres d'appel, certaines autres informations de contexte telles que les registres du processeur peuvent être enregistrées quelque part, et au moment du retour, le La méthode appelée publie une valeur de retour qui est ensuite récupérée par l'appelant et toutes les informations de contexte précédemment enregistrées seront restaurées. la différence de performance entre une approche itérative et une approche récursive réside dans le temps que prennent ces opérations.

Du point de vue de l'implémentation, vous commencez vraiment à remarquer la différence lorsque le temps nécessaire pour gérer le contexte d'appel est comparable au temps nécessaire à l'exécution de votre méthode. Si votre méthode récursive prend plus de temps à exécuter que la partie de gestion du contexte appelant, suivez la voie récursive car le code est généralement plus lisible et facile à comprendre et vous ne remarquerez pas la perte de performances. Sinon, passez par itération pour des raisons d'efficacité.

Je crois que la récursivité de la queue en java n'est pas actuellement optimisée. Les détails sont parsemés tout au long de cette discussion sur LtU et les liens associés. C'est peut- être une fonctionnalité de la prochaine version 7, mais apparemment, cela présente certaines difficultés lorsqu'il est combiné avec Stack Inspection car certains cadres seraient manquants. L'inspection de la pile a été utilisée pour implémenter leur modèle de sécurité à grain fin depuis Java 2.

http://lambda-the-ultimate.org/node/1333

Il existe de nombreux cas où il donne une solution beaucoup plus élégante que la méthode itérative, l'exemple courant étant la traversée d'un arbre binaire, il n'est donc pas nécessairement plus difficile à maintenir. En général, les versions itératives sont généralement un peu plus rapides (et lors de l'optimisation peuvent bien remplacer une version récursive), mais les versions récursives sont plus simples à comprendre et à implémenter correctement.

La récursivité est très utile dans certaines situations. Par exemple, considérons le code pour trouver la factorielle

int factorial ( int input )
{
  int x, fact = 1;
  for ( x = input; x > 1; x--)
     fact *= x;
  return fact;
}

Considérez-le maintenant en utilisant la fonction récursive

int factorial ( int input )
{
  if (input == 0)
  {
     return 1;
  }
  return input * factorial(input - 1);
}

En observant ces deux, nous pouvons voir que la récursivité est facile à comprendre. Mais si elle n'est pas utilisée avec précaution, elle peut aussi être sujette à des erreurs. Supposons que si nous manquons if (input == 0), le code sera exécuté pendant un certain temps et se terminera généralement par un débordement de pile.

Dans de nombreux cas, la récursivité est plus rapide en raison de la mise en cache, ce qui améliore les performances. Par exemple, voici une version itérative du tri par fusion utilisant la routine de fusion traditionnelle. Il s'exécutera plus lentement que l'implémentation récursive en raison de l'amélioration des performances de mise en cache.

Mise en œuvre itérative

public static void sort(Comparable[] a)
{
    int N = a.length;
    aux = new Comparable[N];
    for (int sz = 1; sz < N; sz = sz+sz)
        for (int lo = 0; lo < N-sz; lo += sz+sz)
            merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}

Implémentation récursive

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);
}

PS - c'est ce qu'a dit le professeur Kevin Wayne (Princeton University) sur le cours sur les algorithmes présenté sur Coursera.

En utilisant la récursivité, vous encourez le coût d'un appel de fonction à chaque "itération", alors qu'avec une boucle, la seule chose que vous payez habituellement est une augmentation / diminution. Donc, si le code de la boucle n'est pas beaucoup plus compliqué que le code de la solution récursive, la boucle sera généralement supérieure à la récursivité.

La récursivité et l'itération dépendent de la logique métier que vous souhaitez implémenter, bien que dans la plupart des cas, elle puisse être utilisée de manière interchangeable. La plupart des développeurs optent pour la récursivité car c'est plus facile à comprendre.

Cela dépend de la langue. En Java, vous devez utiliser des boucles. Les langages fonctionnels optimisent la récursivité.

Si vous êtes en train d'itérer sur une liste, alors bien sûr, répétez.

Quelques autres réponses ont mentionné la traversée de l'arbre (en profondeur d'abord). C'est vraiment un excellent exemple, car c'est une chose très courante à faire avec une structure de données très commune. La récursivité est extrêmement intuitive pour ce problème.

Découvrez les méthodes de "recherche" ici: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

La récursivité est plus simple (et donc - plus fondamentale) que toute définition possible d'une itération. Vous pouvez définir un système de Turing complet avec seulement une paire de combinateurs (oui, même une récursivité elle-même est une notion dérivée dans un tel système). Le calcul lambda est un système fondamental tout aussi puissant, doté de fonctions récursives. Mais si vous voulez définir correctement une itération, vous aurez besoin de beaucoup plus de primitives pour commencer.

Quant au code - non, le code récursif est en fait beaucoup plus facile à comprendre et à maintenir qu'un code purement itératif, car la plupart des structures de données sont récursives. Bien sûr, pour bien faire les choses, il faudrait au moins un langage prenant en charge les fonctions et fermetures d'ordre élevé - pour obtenir tous les combinateurs et itérateurs standard de manière ordonnée. En C ++, bien sûr, les solutions récursives complexes peuvent sembler un peu laides, à moins que vous ne soyez un utilisateur hardcore de FC ++ et similaires.

Je pense que dans la récursion (non-queue), il y aurait un impact sur les performances pour allouer une nouvelle pile, etc. chaque fois que la fonction est appelée (en fonction du langage, bien sûr).

cela dépend de la "profondeur de récursivité". cela dépend de l'influence de la surcharge de l'appel de fonction sur le temps d'exécution total.

Par exemple, le calcul de la factorielle classique de manière récursive est très inefficace en raison de: - risque de débordement de données - risque de débordement de pile - la surcharge d'appel de fonction occupe 80% du temps d'exécution

tout en développant un algorithme min-max pour l'analyse de position dans le jeu d'échecs qui analysera les N mouvements ultérieurs peut être implémenté en récursivité sur la "profondeur d'analyse" (comme je le fais ^ _ ^)

Récursivité? Par où commencer, wiki vous dira "c'est le processus de répétition des éléments d'une manière auto-similaire"

À l'époque où je faisais du C, la récursivité C ++ était un envoi divin, des trucs comme "Tail récursion". Vous trouverez également de nombreux algorithmes de tri utilisant la récursivité. Exemple de tri rapide: http://alienryderflex.com/quicksort/

La récursivité est comme tout autre algorithme utile pour un problème spécifique. Peut-être que vous ne trouverez pas une utilisation immédiatement ou souvent, mais il y aura un problème, vous serez content qu'elle soit disponible.

En C ++, si la fonction récursive est un modèle, le compilateur a plus de chance de l'optimiser, car toutes les déductions de type et les instanciations de fonction se produiront lors de la compilation. Les compilateurs modernes peuvent également intégrer la fonction si possible. Donc, si l'on utilise des indicateurs d'optimisation comme -O3ou -O2dans g++, les récursions peuvent avoir la chance d'être plus rapides que les itérations. Dans les codes itératifs, le compilateur a moins de chance de l'optimiser, car il est déjà dans un état plus ou moins optimal (s'il est suffisamment bien écrit).

Dans mon cas, j'essayais d'implémenter l'exponentiation matricielle en quadrature à l'aide d'objets matriciels Armadillo, de manière récursive et itérative. L'algorithme peut être trouvé ici ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring . Mes fonctions ont été modelées et j'ai calculé des 1,000,000 12x12matrices élevées à la puissance 10. J'ai obtenu le résultat suivant:

iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec

iterative + No-optimisation flag  -> 2.83.. sec
recursive + No-optimisation flag  -> 4.15.. sec

Ces résultats ont été obtenus en utilisant gcc-4.8 avec c ++ 11 flag ( -std=c++11) et Armadillo 6.1 avec Intel mkl. Le compilateur Intel affiche également des résultats similaires.

Mike a raison. La récursivité de queue n'est pas optimisée par le compilateur Java ou la JVM. Vous obtiendrez toujours un débordement de pile avec quelque chose comme ceci:

int count(int i) {
  return i >= 100000000 ? i : count(i+1);
}

Vous devez garder à l'esprit qu'en utilisant une récursivité trop profonde, vous rencontrerez Stack Overflow, selon la taille de pile autorisée. Pour éviter cela, assurez-vous de fournir un cas de base qui met fin à votre récursivité.

La récursivité a l'inconvénient que l'algorithme que vous écrivez à l'aide de la récursivité a une complexité d'espace O (n). Bien que l'approche itérative ait une complexité spatiale de O (1), c'est l'avantage d'utiliser l'itération sur la récursivité. Alors pourquoi utilisons-nous la récursivité?

Voir ci-dessous.

Parfois, il est plus facile d'écrire un algorithme à l'aide de la récursivité alors qu'il est légèrement plus difficile d'écrire le même algorithme à l'aide de l'itération.Dans ce cas, si vous choisissez de suivre l'approche d'itération, vous devrez gérer la pile vous-même.

Si les itérations sont atomiques et que les ordres de grandeur sont plus chers que de pousser un nouveau cadre de pile et de créer un nouveau thread et que vous avez plusieurs cœurs et que votre environnement d'exécution peut les utiliser tous, une approche récursive pourrait générer une énorme amélioration des performances lorsqu'elle est combinée avec multithreading. Si le nombre moyen d'itérations n'est pas prévisible, il peut être judicieux d'utiliser un pool de threads qui contrôlera l'allocation des threads et empêchera votre processus de créer trop de threads et de monopoliser le système.

Par exemple, dans certaines langues, il existe des implémentations récursives de tri de fusion multithread.

Mais encore une fois, le multithreading peut être utilisé avec une boucle plutôt qu'avec une récursivité, donc la façon dont cette combinaison fonctionnera dépend de plus de facteurs, y compris le système d'exploitation et son mécanisme d'allocation de threads.

Pour autant que je sache, Perl n'optimise pas les appels récursifs à la queue, mais vous pouvez les simuler.

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

Lors de son premier appel, il allouera de l'espace sur la pile. Ensuite, il changera ses arguments et redémarrera le sous-programme, sans rien ajouter de plus à la pile. Il prétendra donc qu'il ne s'est jamais appelé lui-même, le transformant en un processus itératif.

Notez qu'il n'y a pas de " my @_;" ou " local @_;", sinon vous ne fonctionneriez plus.

En utilisant uniquement Chrome 45.0.2454.85 m, la récursivité semble être une bonne quantité plus rapidement.

Voici le code:

(function recursionVsForLoop(global) {
    "use strict";

    // Perf test
    function perfTest() {}

    perfTest.prototype.do = function(ns, fn) {
        console.time(ns);
        fn();
        console.timeEnd(ns);
    };

    // Recursion method
    (function recur() {
        var count = 0;
        global.recurFn = function recurFn(fn, cycles) {
            fn();
            count = count + 1;
            if (count !== cycles) recurFn(fn, cycles);
        };
    })();

    // Looped method
    function loopFn(fn, cycles) {
        for (var i = 0; i < cycles; i++) {
            fn();
        }
    }

    // Tests
    var curTest = new perfTest(),
        testsToRun = 100;

    curTest.do('recursion', function() {
        recurFn(function() {
            console.log('a recur run.');
        }, testsToRun);
    });

    curTest.do('loop', function() {
        loopFn(function() {
            console.log('a loop run.');
        }, testsToRun);
    });

})(window);

RÉSULTATS

// 100 exécutions en utilisant la boucle standard

100x pour la boucle. Temps de réalisation: 7,683 ms

// 100 exécutions utilisant une approche récursive fonctionnelle avec récursivité de queue

100x course de récursivité. Temps pour terminer: 4.841ms

Dans la capture d'écran ci-dessous, la récursivité gagne à nouveau avec une plus grande marge lorsqu'elle est exécutée à 300 cycles par test

J'ai trouvé une autre différence entre ces approches. Cela semble simple et sans importance, mais il a un rôle très important lorsque vous vous préparez pour des entretiens et que ce sujet se pose, alors regardez attentivement.

En bref: 1) la traversée itérative de post-ordre n'est pas facile - ce qui rend la DFT plus complexe 2) les cycles sont plus faciles à vérifier avec la récursivité

Détails:

Dans le cas récursif, il est facile de créer des traversées pré et post:

Imaginez une question assez standard: "imprimer toutes les tâches qui doivent être exécutées pour exécuter la tâche 5, lorsque les tâches dépendent d'autres tâches"

Exemple:

    //key-task, value-list of tasks the key task depends on
    //"adjacency map":
    Map<Integer, List<Integer>> tasksMap = new HashMap<>();
    tasksMap.put(0, new ArrayList<>());
    tasksMap.put(1, new ArrayList<>());

    List<Integer> t2 = new ArrayList<>();
    t2.add(0);
    t2.add(1);
    tasksMap.put(2, t2);

    List<Integer> t3 = new ArrayList<>();
    t3.add(2);
    t3.add(10);
    tasksMap.put(3, t3);

    List<Integer> t4 = new ArrayList<>();
    t4.add(3);
    tasksMap.put(4, t4);

    List<Integer> t5 = new ArrayList<>();
    t5.add(3);
    tasksMap.put(5, t5);

    tasksMap.put(6, new ArrayList<>());
    tasksMap.put(7, new ArrayList<>());

    List<Integer> t8 = new ArrayList<>();
    t8.add(5);
    tasksMap.put(8, t8);

    List<Integer> t9 = new ArrayList<>();
    t9.add(4);
    tasksMap.put(9, t9);

    tasksMap.put(10, new ArrayList<>());

    //task to analyze:
    int task = 5;


    List<Integer> res11 = getTasksInOrderDftReqPostOrder(tasksMap, task);
    System.out.println(res11);**//note, no reverse required**

    List<Integer> res12 = getTasksInOrderDftReqPreOrder(tasksMap, task);
    Collections.reverse(res12);//note reverse!
    System.out.println(res12);

    private static List<Integer> getTasksInOrderDftReqPreOrder(Map<Integer, List<Integer>> tasksMap, int task) {
         List<Integer> result = new ArrayList<>();
         Set<Integer> visited = new HashSet<>();
         reqPreOrder(tasksMap,task,result, visited);
         return result;
    }

private static void reqPreOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {

    if(!visited.contains(task)) {
        visited.add(task);
        result.add(task);//pre order!
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPreOrder(tasksMap,child,result, visited);
            }
        }
    }
}

private static List<Integer> getTasksInOrderDftReqPostOrder(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    reqPostOrder(tasksMap,task,result, visited);
    return result;
}

private static void reqPostOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {
    if(!visited.contains(task)) {
        visited.add(task);
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPostOrder(tasksMap,child,result, visited);
            }
        }
        result.add(task);//post order!
    }
}

Notez que la traversée récursive post-commande ne nécessite pas une inversion ultérieure du résultat. Les enfants imprimés en premier et votre tâche dans la question imprimée en dernier. Tout va bien. Vous pouvez effectuer une traversée de pré-commande récursive (également illustrée ci-dessus) et celle-ci nécessitera une inversion de la liste des résultats.

Pas si simple avec une approche itérative! Dans l'approche itérative (une pile), vous ne pouvez effectuer qu'une traversée de précommande, vous devez donc inverser le tableau de résultats à la fin:

    List<Integer> res1 = getTasksInOrderDftStack(tasksMap, task);
    Collections.reverse(res1);//note reverse!
    System.out.println(res1);

    private static List<Integer> getTasksInOrderDftStack(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> st = new Stack<>();


    st.add(task);
    visited.add(task);

    while(!st.isEmpty()){
        Integer node = st.pop();
        List<Integer> children = tasksMap.get(node);
        result.add(node);
        if(children!=null && children.size() > 0){
            for(Integer child:children){
                if(!visited.contains(child)){
                    st.add(child);
                    visited.add(child);
                }
            }
        }
        //If you put it here - it does not matter - it is anyway a pre-order
        //result.add(node);
    }
    return result;
}

Ça a l'air simple, non?

Mais c'est un piège dans certaines interviews.

Cela signifie ce qui suit: avec l'approche récursive, vous pouvez implémenter Depth First Traversal puis sélectionner l'ordre dont vous avez besoin avant ou après (simplement en changeant l'emplacement de l '"impression", dans notre cas de "l'ajout à la liste de résultats" ). Avec l'approche itérative (une pile), vous pouvez facilement faire uniquement une traversée de précommande et donc dans la situation où les enfants doivent être imprimés en premier (à peu près toutes les situations où vous devez commencer l'impression à partir des nœuds inférieurs, en remontant) - vous êtes dans le problème. Si vous rencontrez ce problème, vous pouvez revenir en arrière plus tard, mais ce sera un ajout à votre algorithme. Et si un intervieweur regarde sa montre, cela peut vous poser problème. Il existe des façons complexes de faire un parcours itératif de post-commande, elles existent, mais elles ne sont pas simples . Exemple:https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

Ainsi, l'essentiel: j'utiliserais la récursivité lors des entretiens, c'est plus simple à gérer et à expliquer. Vous avez un moyen facile de passer de la traversée pré-post-commande dans tous les cas urgents. Avec itératif, vous n'êtes pas si flexible.

J'utiliserais la récursivité et dirais ensuite: "Ok, mais l'itératif peut me fournir un contrôle plus direct sur la mémoire utilisée, je peux facilement mesurer la taille de la pile et interdire certains débordements dangereux .."

Un autre avantage de la récursivité - il est plus simple d'éviter les cycles / préavis dans un graphique.

Exemple (preudocode):

dft(n){
    mark(n)
    for(child: n.children){
        if(marked(child)) 
            explode - cycle found!!!
        dft(child)
    }
    unmark(n)
}

Il peut être amusant de l'écrire comme récursivité ou comme pratique.

Cependant, si le code doit être utilisé en production, vous devez considérer la possibilité d'un débordement de pile.

L'optimisation de la récursivité de la queue peut éliminer le débordement de pile, mais voulez-vous passer par la difficulté de le faire, et vous devez savoir que vous pouvez compter sur lui pour avoir l'optimisation dans votre environnement.

Chaque fois que l'algorithme se reproduit, quelle est la taille des données ou nréduit de?

Si vous réduisez la taille des données ou nde moitié à chaque fois que vous recursez, vous n'avez généralement pas à vous soucier du débordement de pile. Par exemple, si elle doit avoir une profondeur de 4 000 ou 10 000 niveaux pour que le programme empile le débordement, la taille de vos données doit être d'environ 2 ⁴⁰⁰⁰ pour que votre programme empile le débordement. Pour mettre cela en perspective, un plus grand périphérique de stockage récemment peut contenir 2 ⁶¹ octets, et si vous en avez 2 ⁶¹ , vous n'en avez que 2 . Si vous avez besoin de traiter toutes les données de l'univers et leurs états pour chaque milliseconde depuis la naissance de l'univers estimée à 14 milliards d'années, il se peut que ce ne soit que 2 ¹⁵³ . Donc, si votre programme peut gérer 2 ^{4000 122} tailles de données. Si vous regardez tous les atomes de l'univers, on estime qu'il peut être inférieur à 2 ⁸⁴unités de données ou n, vous pouvez gérer toutes les données de l'univers et le programme ne dépassera pas la pile. Si vous n'avez pas besoin de traiter des nombres aussi grands que 2 ⁴⁰⁰⁰ (un entier de 4000 bits), alors en général, vous n'avez pas à vous soucier du débordement de pile.

Toutefois, si vous réduisez la taille des données ou nd'une quantité constante chaque fois que vous RECURSE, vous pouvez exécuter en débordement de la pile lorsque votre programme fonctionne bien quand nest 1000mais dans une situation, quand ndevient simplement20000 .

Donc, si vous avez un risque de débordement de pile, essayez d'en faire une solution itérative.

Je vais répondre à votre question en concevant une structure de données Haskell par "induction", qui est une sorte de "dual" à récursivité. Et puis je montrerai comment cette dualité mène à de belles choses.

Nous introduisons un type pour un arbre simple:

data Tree a = Branch (Tree a) (Tree a)
            | Leaf a
            deriving (Eq)

Nous pouvons lire cette définition comme disant "Un arbre est une branche (qui contient deux arbres) ou est une feuille (qui contient une valeur de données)". La feuille est donc une sorte de cas minimal. Si un arbre n'est pas une feuille, il doit s'agir d'un arbre composé contenant deux arbres. Ce sont les seuls cas.

Faisons un arbre:

example :: Tree Int
example = Branch (Leaf 1) 
                 (Branch (Leaf 2) 
                         (Leaf 3))

Supposons maintenant que nous voulions ajouter 1 à chaque valeur de l'arborescence. Nous pouvons le faire en appelant:

addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a)     = Leaf (a + 1)

Tout d'abord, notez qu'il s'agit en fait d'une définition récursive. Il prend les constructeurs de données Branch et Leaf comme cas (et puisque Leaf est minimal et ce sont les seuls cas possibles), nous sommes sûrs que la fonction se terminera.

Que faudrait-il pour écrire addOne dans un style itératif? À quoi ressemblera le bouclage dans un nombre arbitraire de branches?

De plus, ce type de récursivité peut souvent être pris en compte, en termes de "foncteur". Nous pouvons transformer les arbres en foncteurs en définissant:

instance Functor Tree where fmap f (Leaf a)     = Leaf (f a)
                            fmap f (Branch a b) = Branch (fmap f a) (fmap f b)

et définir:

addOne' = fmap (+1)

Nous pouvons factoriser d'autres schémas de récursivité, tels que le catamorphisme (ou repli) pour un type de données algébrique. En utilisant un catamorphisme, nous pouvons écrire:

addOne'' = cata go where
           go (Leaf a) = Leaf (a + 1)
           go (Branch a b) = Branch a b

Le débordement de pile ne se produira que si vous programmez dans un langage qui n'a pas de gestion de mémoire intégrée .... Sinon, assurez-vous d'avoir quelque chose dans votre fonction (ou un appel de fonction, STDLbs, etc.). Sans récursivité, il ne serait tout simplement pas possible d'avoir des choses comme ... Google ou SQL, ou n'importe quel endroit où l'on doit trier efficacement de grandes structures de données (classes) ou bases de données.

La récursivité est la voie à suivre si vous souhaitez parcourir les fichiers, vous êtes sûr que c'est ainsi que 'find * | ? grep * 'fonctionne. Un peu à double récursivité, en particulier avec le tuyau (mais ne faites pas un tas d'appels système comme tant de gens aiment le faire si c'est quelque chose que vous allez mettre à la disposition des autres).

Les langages de niveau supérieur et même clang / cpp peuvent l'implémenter de la même manière en arrière-plan.