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 objectif? 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?
Réponses
Trop de publicités?
Leigh Caldwell
Points
4176
Il est possible que la récursivité sera plus cher, en fonction de si la fonction récursive est la queue récursive (la dernière ligne est appel récursif). Récursion sur la queue doit être reconnu par le compilateur et optimisé pour son itératif homologue (tout en conservant le concis, clair de mise en œuvre que vous avez dans votre code).
Je voudrais écrire l'algorithme de la manière la plus logique et la plus claire pour le pauvre meunier (que ce soit vous-même ou quelqu'un d'autre) qui a pour maintenir le code dans quelques mois ou années. Si vous rencontrer des problèmes de performance, alors le profil de votre code, et ensuite, et seulement ensuite, regardez dans l'optimisation de par de se déplacer sur un processus itératif de mise en œuvre. Vous voudrez peut-être chercher dans memoization et la programmation dynamique.
Swift
Points
6363
La comparaison de la récursivité à l'itération, c'est comme comparer un tournevis à tête cruciforme, un tournevis à tête plate. Pour la plupart, vous pourriez supprimer tout cruciforme vis à tête avec une tête plate, mais ce serait plus facile si vous utilisez le tournevis conçu pour que la vis de droite?
Certains algorithmes juste se prêtent à la récursivité en raison de la façon dont ils sont conçus (séquences de Fibonacci, traverser un arbre comme la structure, etc.). La récursivité rend l'algorithme plus concis et plus facile à comprendre (et donc partageables et réutilisables).
Aussi, certains algorithmes récursifs utiliser "Évaluation différée", qui les rend plus efficaces que leurs itératif frères. Cela signifie qu'ils ne le coûteux calculs au moment où ils sont nécessaires plutôt que chaque fois que la boucle s'exécute.
Ce devrait être assez pour vous obtenir a commencé. Je vais déterrer quelques-uns des articles et des exemples pour vous aussi.
Lien 1: Haskel vs PHP (Récursivité vs Itération)
Voici un exemple où le programmeur avait un grand ensemble de données à l'aide de PHP. Il montre comment il aurait été facile à traiter dans Haskel en utilisant la récursivité, mais depuis PHP a pas de moyen facile pour 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: Le Mastering De La Récursivité
La plupart de la récursivité de la mauvaise réputation vient du coût élevé et de l'inefficacité dans des langages impératifs. L'auteur de cet article parle de la façon d'optimiser les algorithmes récursifs pour les rendre plus rapides et plus efficaces. Il se rend également sur la façon de convertir un traditionnel boucle dans une fonction récursive et les avantages de l'utilisation de la fin de la récursivité. Son mot de la fin résume certains de mes points clés je pense:
"récursive de programmation donne au programmeur une meilleure façon d'organiser le code est à la fois facile à entretenir et d'une cohérence logique."
http://www.ibm.com/developerworks/linux/library/l-recurs/index.html
Lien 3: la récursivité Est toujours plus rapide que la boucle? (Réponse)
Voici un lien vers une réponse pour un stackoverflow question qui est semblable à la vôtre. L'auteur souligne que beaucoup de repères associés soit à recursing ou en boucle sont très spécifiques à la langue. Langages sont généralement plus rapide à l'aide d'une boucle et plus lent avec la récursivité, et vice-versa pour les langages fonctionnels. Je suppose que le principal point à prendre à partir de ce lien, c'est qu'il est très difficile de répondre à la question dans une langue agnostique / situation aveugles sens.
Doron Yaacoby
Points
2946
Récurrence est plus coûteux en mémoire, car chaque appel récursif nécessite généralement une adresse de mémoire d’être poussé à la pile - afin que le programme pourrait revenir plus tard sur ce point.
Pourtant, il existe de nombreux cas dans lequel récursivité est beaucoup plus naturelle et plus lisible que boucles - comme quand travailler avec des arbres. Dans ces cas, je recommande de s’en tenir à la récursivité.
zweiterlinde
Points
5984
Généralement, on pourrait s'attendre de la performance peine de mentir dans l'autre sens. Les appels récursifs peut conduire à la construction d'extra pile d'images; la peine pour cette variable. Aussi, dans certains langages comme Python (plus correctement, dans certaines implémentations de certaines langues...), vous pouvez exécuter dans la pile des limites assez facilement pour les tâches que vous pourriez spécifier de manière récursive, comme la recherche de la valeur maximale dans une structure d'arbre de données. Dans ces cas, vous voulez vraiment le bâton avec boucles.
De bien écrire des fonctions récursives peuvent réduire les performances peine un peu, en supposant que vous avez un compilateur optimise la queue récurrences, etc. (Également double vérifier que la fonction est vraiment la queue récursive---c'est une de ces choses que beaucoup de gens font des erreurs.)
En dehors de "bord" des cas (calcul haute performance, très grande profondeur de récursion, etc.), il est préférable d'adopter l'approche qui exprime le plus clairement votre intention, est bien conçu, et il est facile à entretenir. Optimiser seulement après l'identification d'un besoin.
