La récursivité est-elle toujours plus rapide que la boucle?

286

Je sais que la récursion est parfois beaucoup plus propre que la boucle, et je ne demande rien sur le moment où je devrais utiliser la récursion sur l'itération, je sais qu'il y a déjà beaucoup de questions à ce sujet.

Ce que je demande, c'est, la récursivité est-elle toujours plus rapide qu'une boucle? Il me semble que vous seriez toujours en mesure d'affiner une boucle et de la faire fonctionner plus rapidement qu'une fonction récursive car la boucle est constamment absente lors de la configuration de nouveaux cadres de pile.

Je recherche spécifiquement si la récursivité est plus rapide dans les applications où la récursivité est la bonne façon de gérer les données, comme dans certaines fonctions de tri, dans les arbres binaires, etc.

Carson Myers
la source
3
Parfois, la procédure itérative ou les formules sous forme fermée pour certaines récidives mettent des siècles à apparaître. Je pense que dans ces moments, la récursivité est plus rapide :) lol
Pratik Deoghare
24
Pour ma part, je préfère de beaucoup l'itération. ;-)
Iterator
doublon possible de récursivité ou d'itération?
nawfal
@PratikDeoghare Non, la question n'est pas de choisir un algorithme entièrement différent. Vous pouvez toujours convertir une fonction récursive en une méthode fonctionnant de manière identique qui utilise une boucle. Par exemple, cette réponse a le même algorithme au format récursif et en boucle . En général, vous placerez un tuple des arguments de la fonction récursive dans une pile, en poussant vers la pile pour appeler, en vous débarrassant de la pile pour revenir de la fonction.
TamaMcGlinn

Réponses:

358

Cela dépend de la langue utilisée. Vous avez écrit «indépendant de la langue», je vais donc donner quelques exemples.

En Java, C et Python, la récursivité est assez chère par rapport à l'itération (en général) car elle nécessite l'allocation d'un nouveau cadre de pile. Dans certains compilateurs C, on peut utiliser un indicateur de compilateur pour éliminer cette surcharge, qui transforme certains types de récursivité (en fait, certains types d'appels de queue) en sauts au lieu d'appels de fonction.

Dans les implémentations de langage de programmation fonctionnel, parfois, l'itération peut être très coûteuse et la récursivité peut être très bon marché. Dans de nombreux cas, la récursivité est transformée en un simple saut, mais la modification de la variable de boucle (qui est mutable) nécessite parfois des opérations relativement lourdes, en particulier sur les implémentations qui prennent en charge plusieurs threads d'exécution. La mutation est coûteuse dans certains de ces environnements en raison de l'interaction entre le mutateur et le garbage collector, si les deux peuvent s'exécuter en même temps.

Je sais que dans certaines implémentations de Scheme, la récursivité sera généralement plus rapide que la boucle.

En bref, la réponse dépend du code et de l'implémentation. Utilisez le style que vous préférez. Si vous utilisez un langage fonctionnel, la récursivité peut être plus rapide. Si vous utilisez un langage impératif, l'itération est probablement plus rapide. Dans certains environnements, les deux méthodes entraîneront la génération du même assemblage (mettez-le dans votre tuyau et fumez-le).

Addendum: Dans certains environnements, la meilleure alternative n'est ni la récursivité ni l'itération mais plutôt des fonctions d'ordre supérieur. Il s'agit notamment de "carte", "filtre" et "réduire" (qui est également appelé "plier"). Ce sont non seulement le style préféré, non seulement ils sont souvent plus propres, mais dans certains environnements, ces fonctions sont les premières (ou les seules) à bénéficier de la parallélisation automatique - elles peuvent donc être beaucoup plus rapides que l'itération ou la récursivité. Data Parallel Haskell est un exemple d'un tel environnement.

Les compréhensions de liste sont une autre alternative, mais ce ne sont généralement que du sucre syntaxique pour les fonctions d'itération, de récursivité ou d'ordre supérieur.

Dietrich Epp
la source
48
J'ajoute +1 à cela, et je voudrais dire que "récursivité" et "boucles" sont exactement ce que les humains nomment leur code. Ce qui importe pour les performances n'est pas la façon dont vous nommez les choses, mais plutôt la façon dont elles sont compilées / interprétées. La récursivité, par définition, est un concept mathématique et n'a pas grand-chose à voir avec les cadres de pile et les éléments d'assemblage.
P Shved
1
De plus, la récursivité est, en général, l'approche la plus naturelle dans les langages fonctionnels, et l'itération est normalement plus intuitive dans les langages impératifs. Il est peu probable que la différence de performance soit perceptible, alors utilisez simplement ce qui vous semble le plus naturel pour cette langue particulière. Par exemple, vous ne voudriez probablement pas utiliser l'itération dans Haskell lorsque la récursivité est beaucoup plus simple.
Sasha Chedygov
4
Généralement, la récursivité est compilée en boucles, les boucles étant une construction de niveau inférieur. Pourquoi? Parce que la récursivité est généralement bien fondée sur une structure de données, induisant une algèbre F initiale et vous permettant de prouver certaines propriétés sur la terminaison ainsi que des arguments inductifs sur la structure du calcul (récursif). Le processus par lequel la récursivité est compilée en boucles est l'optimisation des appels de queue.
Kristopher Micinski
Ce qui importe le plus, ce sont les opérations non effectuées. Plus vous "IO", plus vous devez traiter. Les données non-E / S (ou indexation) sont toujours la plus grande amélioration des performances de tout système, car vous n'avez pas à les traiter en premier lieu.
Jeff Fischer
53

la récursivité est-elle toujours plus rapide qu'une boucle?

Non, l' itération sera toujours plus rapide que la récursivité. (dans une architecture Von Neumann)

Explication:

Si vous créez les opérations minimales d'un ordinateur générique à partir de zéro, "l'itération" vient d'abord comme un bloc de construction et consomme moins de ressources que la "récursivité", l'ergo est plus rapide.

Construire une pseudo-machine à partir de zéro:

Questionnez-vous : de quoi avez-vous besoin pour calculer une valeur, c'est-à-dire pour suivre un algorithme et atteindre un résultat?

Nous établirons une hiérarchie de concepts, en partant de zéro et en définissant en premier lieu les concepts de base et de base, puis nous construirons des concepts de second niveau avec ceux-ci, etc.

  1. Premier concept: cellules mémoire, stockage, état . Pour faire quelque chose, vous avez besoin de lieux pour stocker les valeurs de résultats finales et intermédiaires. Supposons que nous ayons un tableau infini de cellules "entières", appelées Memory , M [0..Infinite].

  2. Instructions: faites quelque chose - transformez une cellule, changez sa valeur. modifier l'état . Chaque instruction intéressante effectue une transformation. Les instructions de base sont les suivantes:

    a) Définir et déplacer des cellules de mémoire

    • stocker une valeur en mémoire, p.ex.: stocker 5 m [4]
    • copier une valeur dans une autre position: par exemple: stocker m [4] m [8]

    b) Logique et arithmétique

    • et, ou, xor, non
    • ajouter, sous, mul, div. par exemple, ajouter m [7] m [8]
  3. Un agent d'exécution : un cœur dans un processeur moderne. Un "agent" est quelque chose qui peut exécuter des instructions. Un agent peut également être une personne suivant l'algorithme sur papier.

  4. Ordre des étapes: une séquence d'instructions : c'est-à-dire: faites-le d'abord, faites-le ensuite, etc. Une séquence impérative d'instructions. Une seule expression de ligne est "une séquence impérative d'instructions". Si vous avez une expression avec un "ordre d'évaluation" spécifique, alors vous avez des étapes . Cela signifie que même une expression composée unique a des «étapes» implicites et a également une variable locale implicite (appelons-la «résultat»). par exemple:

    4 + 3 * 2 - 5
    (- (+ (* 3 2) 4 ) 5)
    (sub (add (mul 3 2) 4 ) 5)  
    

    L'expression ci-dessus implique 3 étapes avec une variable "résultat" implicite.

    // pseudocode
    
           1. result = (mul 3 2)
           2. result = (add 4 result)
           3. result = (sub result 5)
    

    Ainsi, même les expressions infixes, puisque vous avez un ordre d'évaluation spécifique, sont une séquence impérative d'instructions . L'expression implique une séquence d'opérations à effectuer dans un ordre spécifique, et parce qu'il y a des étapes , il y a aussi une variable intermédiaire "résultat" implicite.

  5. Pointeur d'instruction : Si vous avez une séquence d'étapes, vous avez également un "pointeur d'instruction" implicite. Le pointeur d'instruction marque l'instruction suivante et avance après la lecture de l'instruction mais avant l'exécution de l'instruction.

    Dans cette pseudo-machine informatique, le pointeur d'instructions fait partie de la mémoire . (Remarque: Normalement, le pointeur d'instruction sera un «registre spécial» dans un cœur de processeur, mais ici nous simplifierons les concepts et supposerons que toutes les données (registres inclus) font partie de la «mémoire»)

  6. Saut - Une fois que vous avez un nombre ordonné d'étapes et un pointeur d'instructions , vous pouvez appliquer l' instruction " store " pour modifier la valeur du pointeur d'instructions lui-même. Nous appellerons cette utilisation spécifique de l' instruction store avec un nouveau nom: Jump . Nous utilisons un nouveau nom car il est plus facile de le considérer comme un nouveau concept. En modifiant le pointeur d'instruction, nous demandons à l'agent de «passer à l'étape x».

  7. Itération infinie : en sautant en arrière, vous pouvez maintenant faire en sorte que l'agent "répète" un certain nombre d'étapes. À ce stade, nous avons une itération infinie.

                       1. mov 1000 m[30]
                       2. sub m[30] 1
                       3. jmp-to 2  // infinite loop
    
  8. Conditionnel - Exécution conditionnelle des instructions. Avec la clause "conditionnelle", vous pouvez exécuter conditionnellement l'une des instructions en fonction de l'état actuel (qui peut être défini avec une instruction précédente).

  9. Itération appropriée : Maintenant, avec la clause conditionnelle , nous pouvons échapper à la boucle infinie de l' instruction de saut en arrière . Nous avons maintenant une boucle conditionnelle , puis une itération appropriée

    1. mov 1000 m[30]
    2. sub m[30] 1
    3. (if not-zero) jump 2  // jump only if the previous 
                            // sub instruction did not result in 0
    
    // this loop will be repeated 1000 times
    // here we have proper ***iteration***, a conditional loop.
    
  10. Attribution de noms : attribution de noms à un emplacement de mémoire spécifique contenant des données ou une étape . C'est juste une "commodité". Nous n'ajoutons aucune nouvelle instruction en ayant la capacité de définir des «noms» pour les emplacements de mémoire. «Nommer» n'est pas une instruction pour l'agent, c'est juste une commodité pour nous. La dénomination rend le code (à ce stade) plus facile à lire et plus facile à modifier.

       #define counter m[30]   // name a memory location
       mov 1000 counter
    loop:                      // name a instruction pointer location
        sub counter 1
        (if not-zero) jmp-to loop  
    
  11. Sous-programme à un niveau : supposons qu'il existe une série d'étapes que vous devez exécuter fréquemment. Vous pouvez stocker les étapes dans une position nommée en mémoire, puis passer à cette position lorsque vous devez les exécuter (appel). À la fin de la séquence, vous devrez revenir au point d' appel pour continuer l'exécution. Avec ce mécanisme, vous créez de nouvelles instructions (sous-routines) en composant des instructions de base.

    Mise en œuvre: (aucun nouveau concept requis)

    • Stocker le pointeur d'instruction actuel dans une position de mémoire prédéfinie
    • sauter au sous-programme
    • à la fin de la sous-routine, vous récupérez le pointeur d'instructions à partir de l'emplacement de mémoire prédéfini, en revenant effectivement à l'instruction suivante de l' appel d' origine

    Problème avec l' implémentation à un niveau : vous ne pouvez pas appeler un autre sous-programme à partir d'un sous-programme. Si vous le faites, vous écraserez l'adresse de retour (variable globale), vous ne pourrez donc pas imbriquer d'appels.

    Pour avoir une meilleure implémentation des sous-programmes: Vous avez besoin d'une pile

  12. Pile : Vous définissez un espace mémoire pour fonctionner comme une "pile", vous pouvez "pousser" les valeurs sur la pile, et aussi "pop" la dernière valeur "poussée". Pour implémenter une pile, vous aurez besoin d'un pointeur de pile (similaire au pointeur d'instruction) qui pointe vers la «tête» réelle de la pile. Lorsque vous «poussez» une valeur, le pointeur de pile diminue et vous stockez la valeur. Lorsque vous «sautez», vous obtenez la valeur au pointeur de pile réel, puis le pointeur de pile est incrémenté.

  13. Sous-programmes Maintenant que nous avons une pile, nous pouvons implémenter des sous-programmes appropriés permettant les appels imbriqués . L'implémentation est similaire, mais au lieu de stocker le pointeur d'instruction dans une position de mémoire prédéfinie, nous "poussons" la valeur de l'IP dans la pile . À la fin de la sous-routine, nous venons de «pop» la valeur de la pile, sautant effectivement à l'instruction après l' appel d' origine . Cette implémentation, ayant une «pile» permet d'appeler un sous-programme à partir d'un autre sous-programme. Avec cette implémentation, nous pouvons créer plusieurs niveaux d'abstraction lors de la définition de nouvelles instructions comme sous-programmes, en utilisant des instructions de base ou d'autres sous-programmes comme blocs de construction.

  14. Récursivité : que se passe-t-il lorsqu'un sous-programme s'appelle lui-même?. C'est ce qu'on appelle la «récursivité».

    Problème: L' écrasement des résultats intermédiaires locaux qu'un sous-programme peut stocker en mémoire. Puisque vous appelez / réutilisez les mêmes étapes, si le résultat intermédiaire est stocké dans des emplacements de mémoire prédéfinis (variables globales), il sera écrasé sur les appels imbriqués.

    Solution: pour permettre la récursivité, les sous-programmes doivent stocker les résultats intermédiaires locaux dans la pile . Par conséquent, à chaque appel récursif (direct ou indirect), les résultats intermédiaires sont stockés dans différents emplacements de mémoire.

...

ayant atteint la récursivité nous nous arrêtons ici.

Conclusion:

Dans une architecture Von Neumann, il est clair que "Itération" est un concept plus simple / basique que "Récursion" . Nous avons une forme d ' "Itération" au niveau 7, tandis que "Récursion" est au niveau 14 de la hiérarchie des concepts.

L'itération sera toujours plus rapide dans le code machine car elle implique moins d'instructions donc moins de cycles CPU.

Quel est le meilleur"?

  • Vous devez utiliser "l'itération" lorsque vous traitez des structures de données simples et séquentielles, et partout où une "boucle simple" fera l'affaire.

  • Vous devez utiliser la «récursivité» lorsque vous devez traiter une structure de données récursive (j'aime les appeler «structures de données fractales»), ou lorsque la solution récursive est clairement plus «élégante».

Conseil : utilisez le meilleur outil pour le travail, mais comprenez le fonctionnement interne de chaque outil afin de bien choisir.

Enfin, notez que vous avez de nombreuses possibilités d'utiliser la récursivité. Vous avez des structures de données récursives partout, vous en examinez une maintenant: des parties du DOM supportant ce que vous lisez sont un RDS, une expression JSON est un RDS, le système de fichiers hiérarchique de votre ordinateur est un RDS, c'est-à-dire: vous avez un répertoire racine, contenant des fichiers et des répertoires, chaque répertoire contenant des fichiers et des répertoires, chacun de ces répertoires contenant des fichiers et des répertoires ...

Lucio M. Tato
la source
2
Vous supposez que votre progression est 1) nécessaire et 2) qu'elle s'arrête là où vous l'avez fait. Mais 1) ce n'est pas nécessaire (par exemple, la récursivité peut être transformée en saut, comme l'explique la réponse acceptée, donc aucune pile n'est nécessaire), et 2) elle ne doit pas s'arrêter là (par exemple, éventuellement vous atteindra le traitement simultané, qui pourrait avoir besoin de verrous si vous avez un état mutable comme vous l'avez introduit dans votre 2ème étape, donc tout ralentit; alors qu'une solution immuable comme une fonctionnelle / récursive éviterait le verrouillage, pourrait donc être plus rapide / plus parallèle) .
hmijail pleure les démissionnaires
2
"la récursivité peut être transformée en saut" est faux. Une récursion vraiment utile ne peut pas être transformée en saut. L'appel de queue "récursivité" est un cas spécial, où vous codez "comme récursivité" quelque chose qui peut être simplifié en boucle par le compilateur. Vous confondez également "immuable" avec "récursivité", ce sont des concepts orthogonaux.
Lucio M. Tato
"Une récursion vraiment utile ne peut pas être transformée en saut" -> donc l'optimisation des appels de queue est en quelque sorte inutile? En outre, immuable et récursivité peuvent être orthogonales, mais vous liez le bouclage avec des compteurs mutables - regardez votre étape 9. Il me semble que vous pensez que le bouclage et la récursivité sont des concepts radicalement différents; ils ne le sont pas. stackoverflow.com/questions/2651112/…
hmijail pleure les démissionnaires
@hmijail Je pense qu'un meilleur mot que "utile" est "vrai". La récursivité de queue n'est pas une vraie récursivité car elle utilise simplement la syntaxe d'appel de fonction pour masquer la ramification inconditionnelle, c'est-à-dire l'itération. La véritable récursivité nous fournit une pile de retour en arrière. Cependant, la récursivité de la queue est toujours expressive, ce qui la rend utile. Les propriétés de récursivité qui facilitent ou facilitent l'analyse du code pour l'exactitude sont conférées au code itératif lorsqu'il est exprimé à l'aide d'appels de queue. Bien que cela soit parfois légèrement compensé par des complications supplémentaires dans la version arrière, comme des paramètres supplémentaires.
Kaz
34

La récursivité peut être plus rapide lorsque l'alternative est de gérer explicitement une pile, comme dans les algorithmes de tri ou d'arbre binaire que vous mentionnez.

J'ai eu un cas où la réécriture d'un algorithme récursif en Java l'a rendu plus lent.

Ainsi, la bonne approche consiste à l'écrire d'abord de la manière la plus naturelle, à n'optimiser que si le profilage montre qu'elle est critique, puis à mesurer l'amélioration supposée.

starblue
la source
2
+1 pour "d' abord l'écrire de la manière la plus naturelle " et surtout " n'optimiser que si le profilage montre qu'il est critique "
TripeHound
2
+1 pour avoir reconnu que la pile matérielle peut être plus rapide qu'une pile logicielle implémentée manuellement. Montrant effectivement que toutes les réponses «non» sont incorrectes.
sh1
12

La récursivité de la queue est aussi rapide qu'une boucle. De nombreux langages fonctionnels ont une récursivité de queue implémentée en eux.

mkorpela
la source
35
La récursivité de la queue peut être aussi rapide que le bouclage, lorsqu'une optimisation des appels de queue est implémentée: c2.com/cgi/wiki?TailCallOptimization
Joachim Sauer
12

Considérez ce qui doit absolument être fait pour chacun, itération et récursivité.

  • itération: un saut au début de la boucle
  • récursivité: un saut au début de la fonction appelée

Vous voyez qu'il n'y a pas beaucoup de place pour les différences ici.

(Je suppose que la récursivité est un appel de queue et que le compilateur est conscient de cette optimisation).

Pasi Savolainen
la source
9

La plupart des réponses ici oublient le coupable évident pourquoi la récursivité est souvent plus lente que les solutions itératives. C'est lié à la construction et à la destruction des cadres de pile, mais ce n'est pas exactement cela. C'est généralement une grande différence dans le stockage de la variable automatique pour chaque récursivité. Dans un algorithme itératif avec une boucle, les variables sont souvent conservées dans des registres et même si elles débordent, elles résideront dans le cache de niveau 1. Dans un algorithme récursif, tous les états intermédiaires de la variable sont stockés sur la pile, ce qui signifie qu'ils engendreront beaucoup plus de déversements en mémoire. Cela signifie que même s'il effectue le même nombre d'opérations, il aura beaucoup d'accès à la mémoire dans la boucle chaude et ce qui aggrave, ces opérations de mémoire ont un taux de réutilisation moche, ce qui rend les caches moins efficaces.

Les algorithmes récursifs TL; DR ont généralement un comportement de cache pire que ceux itératifs.

Patrick Schlüter
la source
6

La plupart des réponses ici sont fausses . La bonne réponse est que cela dépend . Par exemple, voici deux fonctions C qui parcourent un arbre. D'abord le récursif:

static
void mm_scan_black(mm_rc *m, ptr p) {
    SET_COL(p, COL_BLACK);
    P_FOR_EACH_CHILD(p, {
        INC_RC(p_child);
        if (GET_COL(p_child) != COL_BLACK) {
            mm_scan_black(m, p_child);
        }
    });
}

Et voici la même fonction implémentée en utilisant l'itération:

static
void mm_scan_black(mm_rc *m, ptr p) {
    stack *st = m->black_stack;
    SET_COL(p, COL_BLACK);
    st_push(st, p);
    while (st->used != 0) {
        p = st_pop(st);
        P_FOR_EACH_CHILD(p, {
            INC_RC(p_child);
            if (GET_COL(p_child) != COL_BLACK) {
                SET_COL(p_child, COL_BLACK);
                st_push(st, p_child);
            }
        });
    }
}

Il n'est pas important de comprendre les détails du code. Ce ne psont que des nœuds et ça P_FOR_EACH_CHILDmarche. Dans la version itérative, nous avons besoin d'une pile explicite stsur laquelle les nœuds sont poussés puis sautés et manipulés.

La fonction récursive s'exécute beaucoup plus rapidement que la fonction itérative. La raison en est que dans ce dernier, pour chaque élément, un CALLà la fonction st_pushest nécessaire, puis un autre à st_pop.

Dans le premier, vous n'avez que le récursif CALLpour chaque nœud.

De plus, l'accès aux variables sur la pile d'appels est incroyablement rapide. Cela signifie que vous lisez de la mémoire qui est susceptible d'être toujours dans le cache le plus interne. Une pile explicite, en revanche, doit être soutenue par malloc: la mémoire du tas, qui est beaucoup plus lente à accéder.

Avec une optimisation minutieuse, comme l'inline st_pushet st_pop, je peux atteindre à peu près la parité avec l'approche récursive. Mais au moins sur mon ordinateur, le coût d'accès à la mémoire de tas est supérieur au coût de l'appel récursif.

Mais cette discussion est essentiellement théorique car la marche récursive dans les arbres est incorrecte . Si vous avez une arborescence suffisamment grande, vous manquerez d'espace de la pile d'appels, c'est pourquoi un algorithme itératif doit être utilisé.

Björn Lindqvist
la source
Je peux confirmer que j'ai rencontré une situation similaire et qu'il existe des situations où la récursivité peut être plus rapide qu'une pile manuelle sur le tas. Surtout lorsque l'optimisation est activée dans le compilateur pour éviter une partie de la surcharge de l'appel d'une fonction.
while1fork
1
A fait une traversée en pré-commande d'un arbre binaire à 7 nœuds 10 ^ 8 fois. Récursivité 25ns. Pile explicite (vérifiée ou non - ne fait pas beaucoup de différence) ~ 15ns. La récursivité doit faire plus (enregistrement et restauration des registres + alignements de trame (généralement) plus stricts) en plus de simplement pousser et sauter. (Et cela empire avec PLT dans les bibliothèques liées dynamiquement.) Vous n'avez pas besoin d'allouer en tas la pile explicite. Vous pouvez faire un obstack dont la première trame se trouve sur la pile d'appels régulière afin de ne pas sacrifier la localité du cache pour le cas le plus courant où vous ne dépassez pas le premier bloc.
PSkocik
3

En général, non, la récursivité ne sera pas plus rapide qu'une boucle dans toute utilisation réaliste qui a des implémentations viables sous les deux formes. Je veux dire, bien sûr, vous pouvez coder des boucles qui prennent une éternité, mais il y aurait de meilleures façons d'implémenter la même boucle qui pourrait surpasser toute implémentation du même problème via la récursivité.

Vous avez mis le doigt sur la tête concernant la raison; créer et détruire des cadres de pile est plus cher qu'un simple saut.

Cependant, notez que j'ai dit "a des implémentations viables sous les deux formes". Pour des choses comme de nombreux algorithmes de tri, il n'y a généralement pas de moyen très viable de les implémenter qui ne configure pas efficacement sa propre version d'une pile, en raison de la génération de "tâches" enfants qui font intrinsèquement partie du processus. Ainsi, la récursivité peut être aussi rapide que la tentative d'implémentation de l'algorithme via le bouclage.

Modifier: Cette réponse suppose des langages non fonctionnels, où la plupart des types de données de base sont mutables. Elle ne s'applique pas aux langages fonctionnels.

ambre
la source
C'est aussi pourquoi plusieurs cas de récursivité sont souvent optimisés par les compilateurs dans les langages où la récursivité est fréquemment utilisée. En F #, par exemple, en plus de la prise en charge complète des fonctions récursives de queue avec l'opcode .tail, vous voyez souvent une fonction récursive compilée en boucle.
em70
Oui. La récursivité de queue peut parfois être le meilleur des deux mondes - la manière fonctionnellement "appropriée" d'implémenter une tâche récursive et les performances d'utilisation d'une boucle.
Ambre
1
Ce n'est pas, en général, correct. Dans certains environnements, la mutation (qui interagit avec GC) est plus coûteuse que la récursivité de queue, qui est transformée en une boucle plus simple dans la sortie qui n'utilise pas de trame de pile supplémentaire.
Dietrich Epp
2

Dans tout système réaliste, non, la création d'un cadre de pile sera toujours plus coûteuse qu'un INC et un JMP. C'est pourquoi de très bons compilateurs transforment automatiquement la récursivité de la queue en un appel à la même trame, c'est-à-dire sans surcharge, de sorte que vous obtenez la version source plus lisible et la version compilée la plus efficace. Un compilateur vraiment, vraiment bon devrait même être capable de transformer la récursivité normale en récursivité de queue là où c'est possible.

Kilian Foth
la source
1

La programmation fonctionnelle concerne davantage « quoi » que « comment ».

Les implémenteurs de langage trouveront un moyen d'optimiser le fonctionnement du code en dessous, si nous n'essayons pas de le rendre plus optimisé qu'il ne devrait l'être. La récursivité peut également être optimisée dans les langues qui prennent en charge l'optimisation des appels de queue.

Ce qui importe plus du point de vue du programmeur, c'est la lisibilité et la maintenabilité plutôt que l'optimisation en premier lieu. Encore une fois, "l'optimisation prématurée est la racine de tout mal".

noego
la source
0

C'est une supposition. Généralement, la récursion ne bat probablement pas souvent ou jamais le bouclage sur des problèmes de taille décente si les deux utilisent de très bons algorithmes (sans compter la difficulté de mise en œuvre), elle peut être différente si elle est utilisée avec un langage avec récursivité d'appel de queue (et un algorithme récursif de queue et avec des boucles également dans le cadre du langage) -qui aurait probablement très similaire et préférerait peut-être même la récursivité une partie du temps.

Roman A. Taycher
la source
0

Selon la théorie, ce sont les mêmes choses. La récursivité et la boucle avec la même complexité O () fonctionneront avec la même vitesse théorique, mais bien sûr la vitesse réelle dépend du langage, du compilateur et du processeur. Exemple avec puissance de nombre peut être codé de manière itérative avec O (ln (n)):

  int power(int t, int k) {
  int res = 1;
  while (k) {
    if (k & 1) res *= t;
    t *= t;
    k >>= 1;
  }
  return res;
  }
Hydrophis Spiralis
la source
1
Big O est «proportionnel à». Les deux le sont donc O(n), mais l'un peut prendre xplus de temps que l'autre, pour tous n.
ctrl-alt-delor