Récursion ou Itération?
https://stackoverflow.com/questions/72209
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Existe-t-il un problème de performance si nous utilisons une boucle au lieu de la récursion ou inversement dans des algorithmes où les deux peuvent servir le même objectif? Ex: Vérifiez si la chaîne donnée est un palindrome. J'ai vu beaucoup de programmeurs utiliser la récursivité pour montrer quand un simple algorithme d'itération peut convenir. Le compilateur joue-t-il un rôle essentiel dans la décision de l’utilisation?
La solution
Il est possible que la récursivité soit plus coûteuse, selon que la fonction récursive est tail récursive (la dernière ligne est un appel récursif). La récursion de queue devrait être reconnue par le compilateur et optimisée par rapport à son homologue itératif (tout en maintenant l'implémentation claire et concise que vous avez dans votre code).
J'écrirais l'algorithme de la manière la plus logique et la plus claire pour le pauvre ventouse (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 uniquement l'optimisation en passant à une implémentation itérative. Vous voudrez peut-être examiner la mémorisation et programmation dynamique .
Autres conseils
Les boucles peuvent améliorer les performances de votre programme. La récursivité peut permettre à votre programmeur de gagner en performances. 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. Dans la plupart des cas, vous pourriez retirer une vis à tête plate à tête cruciforme, mais ce serait plus simple si vous utilisiez le tournevis conçu pour cette vis, non?
Certains algorithmes se prêtent simplement à la récursion en raison de la façon dont ils ont été conçus (séquences de Fibonacci, traversant une structure semblable à une arborescence, 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 "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 qu'à chaque fois que la boucle est exécutée.
Cela devrait suffire à vous aider à démarrer. Je vais chercher des articles et des exemples pour vous aussi.
Lien 1: Haskel contre PHP (Récursivité contre Itération)
Voici un exemple où le programmeur devait traiter un grand ensemble de données en utilisant PHP. Il montre à quel point il aurait été facile de traiter avec Haskel en utilisant la récursivité, mais comme PHP ne disposait d'aucun moyen simple d'accomplir la même méthode, il a été obligé 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îtrise de la récursivité
La plupart de la mauvaise réputation de la récursivité provient 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 l'utilisation de la récursivité en bout de chaîne. Ses derniers mots résument vraiment certains de mes points clés:
"La programmation récursive donne au programmeur une meilleure façon d’organiser code de manière à la fois maintenable et logiquement cohérente. "
Lien 3: La récursivité est-elle toujours plus rapide que la boucle? (Réponse)
Voici un lien vers une réponse à une question similaire à la vôtre. L'auteur souligne qu'un grand nombre de points de repère associés à la récurrence 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 du langage / aveugle.
La récursivité est plus coûteuse en mémoire, car chaque appel récursif nécessite généralement l’ajout d’une adresse mémoire à la pile - pour que le programme puisse ultérieurement y revenir.
Néanmoins, 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 vous recommanderais de vous en tenir à la récursivité.
Généralement, on s’attend à ce que la pénalité de performance se situe dans l’autre sens. Les appels récursifs peuvent conduire à la construction de trames de pile supplémentaires. la pénalité pour cela varie. De plus, dans certains langages tels que Python (plus exactement, dans certaines implémentations de certains langages ...), vous pouvez facilement rencontrer des limites de pile pour les tâches que vous pouvez spécifier de manière récursive, telles que la recherche de la valeur maximale dans une structure de données arborescente. Dans ces cas, vous voulez vraiment vous en tenir à des boucles.
L'écriture de bonnes fonctions récursives peut réduire quelque peu la dégradation des performances, en supposant que vous disposiez d'un compilateur qui optimise les récursions finales, etc. (Vérifiez également que la fonction est réellement récursive --- les gens font des erreurs.)
En dehors de "bord" cas (calcul haute performance, très grande profondeur de récursivité, etc.), il est préférable d’adopter l’approche qui exprime le mieux votre intention, qui est bien conçue et qui peut être maintenue. 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 multiples , de plus petites pièces.
Par exemple, pour créer un algorithme de Fibonnaci récursif, vous devez décomposer fib (n) en fib (n-1) et fib (n-2), puis calculer les deux parties. L’itération ne vous permet que de répéter une fonction encore et encore.
Cependant, Fibonacci est en fait un exemple fragmenté et je pense que l’itération est en réalité 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 une arborescence. Le problème de l'analyse du nœud parent peut être divisé en plusieurs problèmes d'analyse de chaque nœud enfant. Contrairement à l'exemple de Fibonacci, les problèmes les plus petits sont indépendants les uns des autres.
Alors oui, la récursivité est préférable à l'itération pour les problèmes qui peuvent être décomposés en plusieurs problèmes plus petits, indépendants et similaires.
Votre performance se dégrade lors de l’utilisation de la récursivité, car l’appel d’une méthode, quelle que soit sa langue, nécessite beaucoup de préparation: le code appelant affiche une adresse de retour, des paramètres d’appel, certaines autres informations de contexte, telles que les registres du processeur, peuvent être sauvegardées quelque part et heure de retour, la méthode appelée affiche 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 sont restaurées. la diff de performance entre une approche itérative et une approche récursive réside dans le temps que ces opérations prennent.
Du point de vue de la mise en œuvre, 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 l'exécution de votre méthode récursive prend plus de temps que la partie gestion du contexte de l'appelant, procédez 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 éparpillés tout au long de la discussion sur LtU et les liens associés. Cela peut être une fonctionnalité de la version 7 à venir, mais apparemment, il présente certaines difficultés lorsqu'il est combiné à Stack Inspection car certaines images seraient manquantes. Stack Inspection est utilisé depuis Java 2 pour implémenter leur modèle de sécurité détaillé.
Il existe de nombreux cas où cela donne une solution beaucoup plus élégante par rapport à 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 à mettre en œuvre correctement.
La récursion 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;
}
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écursion est facile à comprendre.
Mais si vous ne l'utilisez pas avec précaution, vous risquez également d'être sujet à 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 fonctionnera plus lentement que l'implémentation récursive en raison de la mise en cache des performances améliorées.
Implémentation 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 que le professeur Kevin Wayne (Université de Princeton) a expliqué lors du cours sur les algorithmes présenté sur Coursera.
Avec la récursion, vous payez le coût d'un appel de fonction à chaque "itération", tandis qu'avec une boucle, vous ne payez généralement qu'une incrémentation / décrémentation. Ainsi, si le code de la boucle n'est pas beaucoup plus compliqué que celui de la solution récursive, la boucle sera généralement supérieure à la récursion.
La récursivité et l'itération dépendent de la logique métier que vous souhaitez implémenter, même si dans la plupart des cas, elle peut être utilisée de manière interchangeable. La plupart des développeurs optent pour la récursion car il 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 que parcourir une liste, assurez-vous de le parcourir.
Quelques autres réponses ont mentionné (en premier lieu) la traversée des arbres. C'est vraiment un si bon 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 le " trouver " méthodes 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 complet de Turing avec seulement un paire de combinateurs (oui, même une récursion est une notion dérivée dans un tel système). Le 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.
En ce qui concerne le 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 réussir, il faudrait au moins un langage prenant en charge les fonctions d'ordre élevé et les fermetures, du moins - pour obtenir tous les combinateurs et itérateurs standard. En C ++, bien entendu, les solutions récursives complexes peuvent paraître un peu laides, à moins que vous ne soyez un utilisateur assidu de FC ++ et similaires.
Je pensais qu'en récursion (sans fin) il y aurait un impact sur les performances pour allouer une nouvelle pile, etc. à chaque appel de la fonction (selon la langue, bien sûr).
cela dépend de la "profondeur de récursivité". cela dépend de l’influence du temps système d’appel sur le temps d’exécution total.
Par exemple, calculer la factorielle classique de manière récursive est très inefficace en raison de: - risque de débordement des données - risque de débordement de pile - le temps système d’appel de la fonction occupe 80% du temps d’exécution
tout en développant un algorithme min-max pour l'analyse de la position dans le jeu d'échecs, qui analysera les N mouvements suivants, peut être implémenté en récursion sur la "profondeur d'analyse" (comme je le fais ^ _ ^)
Récursion? Où dois-je commencer, wiki vous dira que c’est le processus de répétition des éléments identique à celui du lecteur "
À l'époque où je faisais la récursion C, C ++ était un don divin, comme "récursion de la queue". Vous découvrirez également que de nombreux algorithmes de tri utilisent la récursivité. Exemple de tri rapide: http://alienryderflex.com/quicksort/
La récursivité est comme tout autre algorithme utile à un problème spécifique. Peut-être ne trouverez-vous pas une utilisation immédiate ou fréquente, mais vous rencontrerez un problème; vous serez heureux de la disponibilité de cette solution.
En C ++, si la fonction récursive est basée sur un modèle, le compilateur a plus de chances de l’optimiser, car toutes les déductions de types et instanciations de fonctions se produiront au moment de la compilation. Les compilateurs modernes peuvent également intégrer la fonction si possible. Ainsi, si l'on utilise des indicateurs d'optimisation tels que -O3 ou -O2 dans g ++ , les récurrences peuvent avoir la chance d'être plus rapides que les itérations. Dans les codes itératifs, le compilateur a moins de chances de l’optimiser, car il est déjà à l’état plus ou moins optimal (s’il est suffisamment écrit).
Dans mon cas, j’essayais de mettre en œuvre l’exponentiation matricielle en effectuant une 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é modélisées et j'ai calculé des 12x12 matrices générées à 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 avec 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 queue n'est pas optimisée par le compilateur Java ou la machine virtuelle Java. Vous obtiendrez toujours un dépassement de pile avec quelque chose comme ceci:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
N'oubliez pas qu'en utilisant une récursion trop profonde, vous rencontrerez un débordement de pile, en fonction de la taille de pile autorisée. Pour éviter cela, veillez à fournir un scénario de base mettant fin à la récursivité.
La récursivité présente l'inconvénient que l'algorithme que vous écrivez à l'aide de la récursion présente une complexité d'espace O (n). Bien que les approches itératives aient une complexité d’espace de O (1), c’est l’avantage d’utiliser l’itération par rapport à 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écursivité alors qu'il est un peu plus difficile d'écrire le même algorithme en utilisant l'itération. Dans ce cas, si vous choisissez de suivre l'approche par itération, vous devrez gérer la pile vous-même.
Autant que je sache, Perl n'optimise pas les appels en fin de parcours, 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 va changer ses arguments et redémarrer le sous-programme, sans rien ajouter de plus à la pile. Il va donc prétendre 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 " mon @_; ". ou " local @_; ", si vous le faisiez, cela ne fonctionnerait plus.
En utilisant seulement Chrome 45.0.2454.85 m, la récursion semble être beaucoup plus rapide.
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 utilisant la boucle standard
100x pour l'exécution en boucle. Temps d'exécution: 7.683ms
// 100 exécutions utilisant une approche récursive fonctionnelle avec récursion de queue
100x exécution récursive. Temps de réalisation: 4.841ms
Dans la capture d'écran ci-dessous, la récursivité gagne à nouveau avec une marge plus importante lorsqu'elle est exécutée à 300 cycles par test
Si les itérations sont atomiques et que les ordres de grandeur sont plus coûteux que de pousser un nouveau cadre de pile et en créant un nouveau fil et , vous avez plusieurs cœurs et votre environnement d’exécution peut tous les utiliser, puis une approche récursive pourrait améliorer considérablement les performances lorsqu’elle est combinée avec le 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 de tri par fusion multithread récursives.
Mais encore une fois, le multithreading peut être utilisé avec la boucle 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.
Je vais répondre à votre question en concevant une structure de données Haskell par "induction", qui est une sorte de "double". à la récursion. Et ensuite, 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 indiquant "Un arbre est une branche (qui contient deux arbres) ou une feuille (qui contient une valeur de données)". Donc, la feuille est 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))
Maintenant, supposons que nous voulions ajouter 1 à chaque valeur de l’arbre. 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 faut les cas des constructeurs de données Branch et Leaf (et comme Leaf est minime et qu’ils sont les seuls cas possibles), nous sommes certains que la fonction se terminera.
Que faudrait-il pour écrire addOne dans un style itératif? À quoi ressemblera la boucle dans un nombre arbitraire de branches?
De plus, ce type de récursion 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éfinissant:
addOne' = fmap (+1)
Nous pouvons exclure d'autres schémas de récursivité, tels que le catamorphisme (ou repliement) d'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
Un 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 éléments tels que ... Google ou SQL, ou n'importe quel endroit où l'on doit trier efficacement de grandes structures de données (classes) ou des bases de données.
La récursion est la voie à suivre si vous souhaitez parcourir les fichiers, vous êtes sûr que c'est comme ça que 'find * | ? grep * 'fonctionne. C'est un peu la double récursion, surtout avec le tuyau (mais ne faites pas une série d'appels système comme beaucoup aiment le faire si c'est quelque chose que vous allez mettre là-bas pour que les autres puissent l'utiliser).
Les langages de niveau supérieur et même clang / cpp peuvent le mettre en œuvre de la même manière en arrière-plan.
