Toutes les fonctions récursives peuvent-elles être codées avec des itérations? [fermé]

10

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?

OscarRyz
la source

Réponses:

10

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
J'ai compris. Alors, quel avantage aurait la récursivité? Simplicité?
OscarRyz
2
@OscarRyz: Oui, et c'est plus élégant.
Michael K
@OscarRyz, la façon dont je l'ai décrit est la récursivité. Cela n'est tout simplement pas fait avec des instructions CPU natives. Le faire manuellement vous permet de faire des choses - comme la parallélisation - qui correspondent mal aux instructions natives.
15

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.

David Thornley
la source
8
Je dirais que le droit est toujours meilleur que rapide. Un code qui fait la mauvaise chose très rapidement n'est pas très bon pour personne.
Mason Wheeler
1
Mais que faire si vous pouvez faire cette mauvaise chose très rapidement?!
RationalGeek
1
@jkohlhepp - Je peux résoudre n'importe quel problème instantanément. La réponse est 0.
Note à soi-même - pensez à un nom
2
L'utilisation de la récursivité plutôt que d'une pile explicite peut être plus efficace, évitant ainsi la nécessité d'allocations de segment de mémoire, la fragmentation possible de la mémoire et les éventuels problèmes de localité. Cependant, «à droite est normalement mieux que rapide», le débordement de pile dans les cas où votre logiciel doit gérer signifie que votre code est cassé. Habituellement, les cas problématiques sont assez faciles à repérer - la récursivité sur un arbre (raisonnablement) équilibré est bonne, mais la récursivité sur un arbre qui peut être très déséquilibré, ou sur une liste chaînée, peut être un bug sérieux dans une langue comme C. Pire , il peut survivre à de simples tests et ne planter que lorsqu'il est déployé pour de vrai.
Steve314
1
Je pense que vous comprenez tous ce que Mason voulait dire et faites juste des blagues pour le plaisir. Bien sûr, un programme correct lent est plus utile qu'un programme incorrect rapide.
Giorgio
4

Quels sont les avantages de la récursivité?

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?

Est-il possible d'avoir une version itérative d'une fonction récursive?

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.

Dima
la source
3

Quels sont les avantages de la récursivité?

Simplicité. Sans optimisation des appels de queue, cela prend bien sûr plus de ressources (pile), mais comment implémenteriez-vous, par exemple, deltreeen Java sans récursivité? La torsion est que vous delete()ne pouvez supprimer des répertoires que s'ils sont vides; voici avec récursivité:

deltree(File fileOrDirectory) {
    if (fileOrDirectory.isDirectory()) {
        for (File subFileOrDirectory : fileOrDirectory.listFiles()) {
            deltree(subFileOrDirectory);
        }
    }
    fileOrDirectory.delete();
}
Joonas Pulakka
la source
1
Avec une pile, comme mentionné par d'autres réponses.
Nicole
Oui, mais c'est simple? -)
Joonas Pulakka
Oh, la récursivité est définitivement meilleure. Je pensais que tu disais que ce n'était pas possible.
Nicole
0

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:

  1. Tout d'abord, penser la "voie récursive" d'un algorithme n'est pas facile. Construire une fonction comme une factorielle (n!) Ou quelque chose comme Hanoi Towers n'est que la pointe de l'iceberg, et atteindre le fond nécessite un temps très long.
  2. Ne pensez pas que la récursivité apporte de la simplicité uniquement dans votre code, parfois, la manière itérative est laide et désordonnée, mais est rentable (regardez la solution récursive du problème de Fibonacci)

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!

David Conde
la source