Est-il correct de dire que partout où la récursion est utilisée une for boucle pourrait être utilisée ? Et si la récursion est généralement plus lente, quelle est la raison technique pour ne jamais l'utiliser au lieu de la boucle ? for itération de la boucle ?
Et s'il est toujours possible de convertir une récursion en une for loop existe-t-il une méthode empirique pour le faire ?
Oui, comme a déclaré par Thanakron Tandavas ,
La récursion est utile lorsque vous résolvez un problème qui peut être résolu par la technique "diviser pour régner".
Par exemple : Tours de Hanoi
Je crois me souvenir que mon professeur d'informatique avait dit à l'époque que tous les problèmes qui ont des solutions récursives ont aussi des solutions itératives. Il dit qu'une solution récursive est généralement plus lente, mais qu'elle est fréquemment utilisée lorsqu'elle est plus facile à raisonner et à coder que les solutions itératives.
Cependant, dans le cas de solutions récursives plus avancées, je ne pense pas qu'il sera toujours possible de les implémenter en utilisant un simple for boucle.
La plupart des réponses semblent supposer que iterative = for loop . Si votre boucle for n'est pas limitée ( a la C, vous pouvez faire ce que vous voulez avec votre compteur de boucle), alors c'est correct. Si c'est un réel for (comme en Python ou dans la plupart des langages fonctionnels où il n'est pas possible de modifier manuellement le compteur de la boucle), alors c'est no correct.
Toutes les fonctions (calculables) peuvent être implémentées à la fois de manière récursive et à l'aide de while des boucles (ou des sauts conditionnels, qui sont en fait la même chose). Si vous vous limitez vraiment à for loops vous n'obtiendrez qu'un sous-ensemble de ces fonctions (les fonctions récursives primitives, si vos opérations élémentaires sont raisonnables). Il s'agit d'un sous-ensemble assez large qui contient toutes les fonctions que vous êtes susceptibles de rencontrer en pratique.
Ce qui est beaucoup plus important, c'est que de nombreuses fonctions sont très faciles à mettre en œuvre de manière récursive et terriblement difficiles à mettre en œuvre de manière itérative (la gestion manuelle de votre pile d'appels ne compte pas).
La récursion + la mémorisation peuvent conduire à une solution plus efficace qu'une approche purement itérative, par exemple en vérifiant ceci : http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
