Quels sont les avantages de la récursivité?
Certains langages de programmation peuvent optimiser la récursivité de queue, mais, toujours en termes généraux, la récursivité consomme plus de ressources que les boucles régulières.
Est-il possible d'avoir une version itérative d'une fonction récursive?
recursion
advantages
OscarRyz
la source
la source
Réponses:
Oui, vous pouvez coder des fonctions récursives sous forme d'itérations. Il vous oblige essentiellement à conserver manuellement les informations qui autrement auraient été gérées par la méthode appelant le code généré par le compilateur.
En d'autres termes, vous avez besoin d'une pile où chaque entrée est une structure contenant les paramètres passés et toutes les variables locales. Vous travaillez toujours sur l'entrée la plus haute de la pile. Si vous devez vous appeler, créez une nouvelle entrée et placez-la sur la pile. Une fois terminé, prenez l'entrée la plus haute de la pile exposant celle ci-dessous et utilisez l'entrée précédemment la plus haute pour extraire les valeurs de retour et mettre à jour la nouvelle entrée la plus haute en conséquence.
Je vous suggère d'étudier un livre de compilation pour voir comment cela est généralement implémenté dans le code machine.
la source
La récursivité est souvent une façon plus naturelle de voir les choses que l'itération. Par exemple, considérez la traversée dans l'ordre d'un arbre binaire:
inorder(left); process(); inorder(right);
est beaucoup plus simple que de maintenir explicitement une pile.Tant que vous n'allez pas trop loin (souffler la pile), la différence d'utilisation des ressources est généralement triviale. Ne vous en faites pas en général. Le code simple est généralement meilleur que le code optimisé à la main, bien qu'il existe des exceptions. Droite est normalement mieux que rapide.
Tout algorithme récursif peut être exprimé comme un algorithme itératif, mais vous devrez peut-être conserver une pile explicite (correspondant à la pile d'appels gérée implicitement). Après tout, si vous compilez une fonction récursive, vous obtenez quelque chose qui repose sur la manipulation d'une pile et le bouclage de la fonction, et c'est itératif.
Les fonctions récursives de queue peuvent être facilement traduites en boucles, et n'ont pas besoin d'une pile, mais c'est un cas spécial.
la source
Essayez de résoudre le problème des tours de Hanoi de manière itérative. Une fois que vous avez abandonné, jetez un œil à la solution itérative et comparez- la à la solution récursive. Lequel est le plus simple?
Oui, en principe. Cependant, pour de nombreux problèmes, y compris des tâches très courantes, telles que les traversées d'arbres, les solutions récursives sont beaucoup plus simples et plus élégantes que les solutions itératives.
la source
Simplicité. Sans optimisation des appels de queue, cela prend bien sûr plus de ressources (pile), mais comment implémenteriez-vous, par exemple,
deltree
en Java sans récursivité? La torsion est que vousdelete()
ne pouvez supprimer des répertoires que s'ils sont vides; voici avec récursivité:la source
Je crois que la récursivité est l'un de ces outils qu'un programmeur doit avoir pour vivre. Avec la récursivité, vous pouvez «penser» vos algorithmes et les résoudre exactement comme vous le pensiez. Mais, je dois vous avertir, tout le monde parle de la beauté de la récursivité et de la simplicité du code, à ce sujet, j'ai quelques choses à dire:
Ayant ces choses à l'esprit, apprenez la récursivité! c'est drôle, complexe et ça vous brisera le cerveau !, mais vous vous retrouverez à l'adorer.
Bonne chance!
la source