Récursion ou Itération?

Y a-t-il un impact sur la performance si nous utilisons la boucle au lieu de la récursivité ou vice versa dans les algorithmes où les deux peuvent servir le même objective? Par exemple: Vérifiez si la chaîne donnée est palindrome. J’ai vu de nombreux programmeurs utiliser la récursivité comme un moyen de montrer qu’un simple algorithme d’itération peut s’adapter à la facture. Le compilateur joue-t-il un rôle essentiel dans la décision de l’utilisation?

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

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

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

Comparer la récursivité à l’itération, c’est comme comparer un tournevis cruciforme à un tournevis à tête plate. Pour la plupart, vous pourriez enlever toute vis à tête cruciforme avec une tête plate, mais ce serait plus facile si vous utilisiez le tournevis conçu pour cette vis juste?

Certains algorithmes se prêtent simplement à la récursivité en raison de la manière dont ils sont conçus (séquences Fibonacci, traversant une structure arborescente, etc.). La récursivité rend l’algorithme plus succinct et plus facile à comprendre (donc partageable et réutilisable).

En outre, certains algorithmes récursifs utilisent “Lazy Evaluation”, ce qui les rend plus efficaces que leurs frères itératifs. Cela signifie qu’ils ne font que les calculs coûteux au moment où ils sont nécessaires plutôt que chaque fois que la boucle s’exécute.

Cela devrait suffire pour vous lancer. Je vais chercher des articles et des exemples pour vous aussi.

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

Voici un exemple où le programmeur devait traiter un grand dataset en utilisant PHP. Il montre à quel point il aurait été facile de faire de la récursivité dans Haskel, mais comme PHP n’avait pas de moyen simple pour accomplir la même méthode, il était obligé d’utiliser une itération pour obtenir le résultat.

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

Lien 2: Révolution de la maîsortingse

La mauvaise réputation de la récursivité provient en grande partie des coûts élevés et de l’inefficacité des langages impératifs. 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 la récursion de bout en bout. Ses derniers mots résument bien certains de mes points clés:

“La programmation récursive donne au programmeur une meilleure façon d’organiser le code d’une manière à la fois maintenable et cohérente sur le plan logique.”

http://www.ibm.com/developerworks/linux/library/l-recurs/index.html

Lien 3: La récursivité est-elle 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 beaucoup de points de référence associés à la récursivité ou à la mise en boucle sont très spécifiques au langage. Les langages impératifs sont généralement plus rapides avec une boucle et plus lents avec la récursivité et inversement 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 agnostique par rapport au langage / situation.

La récursivité est-elle 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 qu’une adresse mémoire soit transmise à la stack – afin que le programme puisse plus tard revenir à ce point.

Cependant, il existe de nombreux cas où 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 restr à la récursivité.

En règle générale, on pourrait s’attendre à ce que la pénalité de performance se situe dans l’autre sens. Les appels récursifs peuvent mener à la construction de trames de stack supplémentaires; la pénalité pour ceci varie. De même, dans certaines langues comme Python (plus correctement, dans certaines implémentations de certains langages …), vous pouvez exécuter des limites de stack assez facilement pour des tâches que vous pourriez spécifier de manière récursive, comme trouver la valeur maximale dans une structure de données arborescente. Dans ces cas, vous voulez vraiment restr avec les boucles.

Ecrire de bonnes fonctions récursives peut réduire quelque peu la performance, en supposant que vous ayez un compilateur qui optimise les récursions de la queue, etc. (Vérifiez également que la fonction est réellement récursive). sur.)

Mis à part les cas “extrêmes” (calcul haute performance, profondeur de récursivité très importante, etc.), il est préférable d’adopter l’approche qui exprime le mieux votre intention, qui est bien conçue et qui soit maintenable. Optimiser uniquement après avoir identifié un besoin.

La récursivité est préférable à l’itération pour les problèmes pouvant être divisés en plusieurs parties plus petites.

Par exemple, pour créer un algorithme récursif de Fibonnaci, 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 qu’une seule fonction à plusieurs resockets.

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’parsing du nœud parent peut être décomposé en plusieurs problèmes plus petits d’parsing de chaque nœud enfant. Contrairement à l’exemple de Fibonacci, les problèmes les plus petits 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 lorsqu’on utilise la récursivité, car appeler une méthode, dans n’importe quelle langue, implique beaucoup de préparation: le code appelant affiche une adresse de retour, des parameters d’appel, d’autres informations de contexte telles que des registres de processeurs. La méthode appelée envoie une valeur de retour qui est ensuite extraite par l’appelant, et toute information de contexte précédemment enregistrée sera restaurée. 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 sharepoint vue de la mise en œuvre, vous commencez vraiment à remarquer la différence lorsque le temps requirejs pour traiter 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 à s’exécuter que la partie de gestion du contexte appelant, passez de manière récursive car le code est généralement plus lisible et facile à comprendre et vous ne remarquerez pas la perte de performances. Sinon, allez itératif pour des raisons d’efficacité.

Je pense que la récursion de la queue en Java n’est pas optimisée pour le moment. Les détails sont disséminés tout au long de cette discussion sur LtU et les liens associés. Il pourrait s’agir d’une fonctionnalité de la prochaine version 7, mais il semble que cela présente certaines difficultés lorsqu’il est associé à l’inspection de la stack, car certaines images seraient manquantes. Stack Inspection a été utilisé pour implémenter leur modèle de sécurité à granularité fine depuis Java 2.

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

Il y a beaucoup de cas où cela donne une solution beaucoup plus élégante que la méthode itérative, l’exemple le plus courant étant la traversée d’un arbre binary, donc ce n’est 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 le factoriel

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

Maintenant, considérez-le en utilisant la fonction récursive

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

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

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 sorting de fusion utilisant la routine de fusion traditionnelle. Il fonctionnera plus lentement que l’implémentation récursive en raison des performances améliorées de la 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 (Université de Princeton) sur le cours sur les algorithmes présentés sur Coursera.

En utilisant la récursivité, vous payez le coût d’un appel de fonction à chaque “itération”, alors qu’avec une boucle, la seule chose que vous payez habituellement est un incrément / décrément. 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 à implémenter, même si, dans la plupart des cas, elle peut être utilisée de manière interchangeable. La plupart des développeurs vont pour la récursivité parce que 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 ne faites qu’itérer une liste, assurez-vous de l’itérer.

Quelques autres réponses ont mentionné la traversée d’arbre (en profondeur d’abord). C’est vraiment un excellent exemple, car c’est une chose très commune à 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 “trouver” 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 Turing-complet avec seulement une paire de combinateurs (oui, même une récursivité est une notion dérivée dans un tel système). Lambda calculus est un système fondamental tout aussi puissant, doté de fonctions récursives. Mais si vous voulez définir une itération correctement, 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, puisque 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 les fermetures d’ordre élevé – pour obtenir tous les combinateurs et les iterators standard de manière ordonnée. En C ++, bien sûr, les solutions récursives compliquées peuvent paraître un peu moche, à moins que vous ne soyez un utilisateur expérimenté de FC ++ et d’autres.

Je pense que dans la récursion (non la queue), il y aurait un problème de performance pour allouer une nouvelle stack, etc. chaque fois que la fonction est appelée (en fonction de la langue, bien sûr).

cela dépend de la “profondeur de récursion”. cela dépend de combien la surcharge de l’appel de la fonction influencera le temps total d’exécution.

Par exemple, le calcul du factoriel classique de manière récursive est très inefficace en raison: – du risque de débordement des données – du risque de débordement de la stack – la surcharge d’appel des fonctions occupe 80% du temps d’exécution

tout en développant un algorithme min-max pour l’parsing de position dans le jeu d’échecs qui parsingra les N mouvements suivants peut être implémenté en récursivité sur la “profondeur d’parsing” (comme je le fais ^ _ ^)

Récursivité? Où est-ce que je commence, wiki vous dira “c’est le processus de répéter des éléments d’une manière similaire”

En ce jour où je faisais du C, la récursion C ++ était un don de Dieu, des choses comme “Récursion de la queue”. Vous trouverez également de nombreux algorithmes de sorting utilisant la récursivité. Exemple de sorting 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 peut-être pas une utilisation immédiate ou fréquente, mais il y aura un problème, vous serez heureux de sa disponibilité.

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 toutes les instanciations de fonctions se produiront au moment de la compilation. Les compilateurs modernes peuvent également intégrer la fonction si possible. Donc, si l’on utilise des indicateurs d’optimisation tels que -O3 ou -O2 dans g++ , les récursions risquent 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 écrit).

Dans mon cas, j’essayais d’implémenter une exponentiation masortingcielle en utilisant des objects de masortingce 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é modélisées et j’ai calculé 1,000,000 masortingces 12x12 scopes à la puissance 10 . J’ai eu 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 l’indicateur c ++ 11 ( -std=c++11 ) et Armadillo 6.1 avec Intel mkl. Le compilateur Intel affiche également des résultats similaires.

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

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

Vous devez garder à l’esprit que l’utilisation d’une récursion trop profonde entraînera un dépassement de stack, en fonction de la taille de stack autorisée. Pour éviter cela, assurez-vous de fournir un cas de base qui finira votre récursivité.

La récursivité présente l’inconvénient que l’algorithme que vous écrivez en utilisant la récursivité a la complexité d’espace O (n). Alors que les approches itératives ont une complexité d’espace de O (1), il s’agit de 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 en utilisant la récursion alors qu’il est légèrement plus difficile d’écrire le même algorithme en utilisant l’itération. Dans ce cas, si vous choisissez de suivre l’approche d’itération, vous devrez gérer la stack vous-même.

À ma connaissance, Perl n’optimise pas les appels récursifs, mais vous pouvez le simuler.

 sub f{ my($l,$r) = @_; if( $l >= $r ){ return $l; } else { # return f( $l+1, $r ); @_ = ( $l+1, $r ); goto &f; } } 

Lorsqu’il sera appelé pour la première fois, il allouera de l’espace sur la stack. Ensuite, il changera ses arguments et redémarrera le sous-programme sans rien append de plus à la stack. Il va donc prétendre qu’il ne s’est jamais appelé, en le transformant en un processus itératif.

Notez qu’il n’y a pas ” my @_; ” ou ” local @_; ” si vous ne le faites pas, cela ne fonctionnerait plus.

Si les itérations sont atomiques et des ordres de grandeur plus chers que de pousser une nouvelle trame de stack et de créer un nouveau thread et que vous avez plusieurs cœurs et que votre environnement d’exécution les utilise tous, une approche récursive 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 bloquer le système.

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

Mais encore une fois, le multithreading peut être utilisé avec le bouclage plutôt que la récursivité. Le fonctionnement de cette combinaison dépend donc de plusieurs facteurs, notamment du système d’exploitation et de son mécanisme d’allocation de threads.

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

Voici le code:

 (function recursionVsForLoop(global) { "use ssortingct"; // 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écute en utilisant la norme pour la boucle

100x pour la boucle en boucle. Temps nécessaire pour terminer: 7.683ms

// 100 exécute une approche récursive fonctionnelle avec récursivité arrière

100 récursivité Temps pour compléter: 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

La récursivité gagne encore!

Je vais répondre à votre question en concevant une structure de données Haskell par “induction”, qui est une sorte de “double” à la 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 suit: “Un arbre est une twig (qui contient deux arbres) ou 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 voulons append 1 à chaque valeur de l’arbre. Nous pouvons le faire en appelant:

 addOne :: Tree Int -> Tree Int addOne (Branch ab) = 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 sums sûrs que la fonction se terminera.

Que faudrait-il pour écrire addOne dans un style itératif? À quoi ressemblera la mise en boucle dans un nombre arbitraire de twigs?

En outre, ce type de récursivité peut souvent être exclu en termes de “foncteur”. Nous pouvons faire des arbres dans des foncteurs en définissant:

 instance Functor Tree where fmap f (Leaf a) = Leaf (fa) fmap f (Branch ab) = Branch (fmap fa) (fmap fb) 

et définir:

 addOne' = fmap (+1) 

Nous pouvons prendre en compte d’autres schémas de récursion, tels que le catamorphisme (ou le pli) pour un type de données algébrique. En utilisant un catamorphisme, on peut écrire:

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

Le débordement de la stack ne se produira que si vous programmez dans une langue sans gestion de la mémoire intégrée …. Sinon, assurez-vous que vous avez 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 sortinger efficacement de grandes structures de données (classes) ou bases de données.

La récursivité est la voie à suivre si vous voulez parcourir les fichiers, c’est sûr que c’est comme ça: «trouver * | ? grep * ‘fonctionne. Un peu de récursivité, en particulier avec le pipe (mais ne faites pas un tas de syscalls comme tant d’autres si vous voulez les utiliser).

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.