En commençant à apprendre le lisp, je suis tombé sur le terme récursif de queue . Qu'est-ce que cela signifie exactement?
1697
En commençant à apprendre le lisp, je suis tombé sur le terme récursif de queue . Qu'est-ce que cela signifie exactement?
Réponses:
Considérons une fonction simple qui ajoute les N premiers nombres naturels. (par exemple
sum(5) = 1 + 2 + 3 + 4 + 5 = 15
).Voici une implémentation JavaScript simple qui utilise la récursivité:
Si vous avez appelé
recsum(5)
, voici ce que l'interpréteur JavaScript évaluerait:Notez comment chaque appel récursif doit se terminer avant que l'interpréteur JavaScript commence réellement à effectuer le travail de calcul de la somme.
Voici une version récursive de la même fonction:
Voici la séquence d'événements qui se produirait si vous appeliez
tailrecsum(5)
, (ce qui serait effectivementtailrecsum(5, 0)
, en raison du deuxième argument par défaut).Dans le cas récursif de queue, à chaque évaluation de l'appel récursif, le
running_total
est mis à jour.Remarque: La réponse d'origine utilisait des exemples de Python. Ceux-ci ont été modifiés en JavaScript, car les interprètes Python ne prennent pas en charge l' optimisation des appels de queue . Cependant, bien que l'optimisation des appels de queue fasse partie de la spécification ECMAScript 2015 , la plupart des interprètes JavaScript ne la prennent pas en charge .
la source
tail recursion
on peut y parvenir dans un langage qui n'optimise pas les appels distants.Dans la récursivité traditionnelle , le modèle typique est que vous effectuez d'abord vos appels récursifs, puis vous prenez la valeur de retour de l'appel récursif et calculez le résultat. De cette manière, vous n'obtenez le résultat de votre calcul que lorsque vous êtes revenu de chaque appel récursif.
Dans la récursivité de queue , vous effectuez d'abord vos calculs, puis vous exécutez l'appel récursif, en passant les résultats de votre étape actuelle à l'étape récursive suivante. Il en résulte que la dernière instruction est sous la forme de
(return (recursive-function params))
. Fondamentalement, la valeur de retour de toute étape récursive donnée est la même que la valeur de retour du prochain appel récursif .La conséquence de cela est qu'une fois que vous êtes prêt à effectuer votre prochaine étape récursive, vous n'avez plus besoin du cadre de pile actuel. Cela permet une certaine optimisation. En fait, avec un compilateur correctement écrit, vous ne devriez jamais avoir un snicker de débordement de pile avec un appel récursif de queue. Réutilisez simplement le cadre de pile actuel pour la prochaine étape récursive. Je suis sûr que Lisp fait ça.
la source
Un point important est que la récursivité de la queue est essentiellement équivalente au bouclage. Ce n'est pas seulement une question d'optimisation du compilateur, mais un fait fondamental sur l'expressivité. Cela va dans les deux sens: vous pouvez prendre n'importe quelle boucle du formulaire
où
E
etQ
sont des expressions etS
est une séquence d'instructions, et la transformer en une fonction récursive de queueBien sûr,
E
,S
etQ
doivent être définies pour calculer une valeur intéressante sur certaines variables. Par exemple, la fonction de bouclageest équivalent à la ou aux fonctions récursives de queue
(Cet "encapsulage" de la fonction récursive de queue avec une fonction avec moins de paramètres est un idiome fonctionnel courant.)
la source
else { return k; }
peut être changé enreturn k;
Cet extrait du livre Programming in Lua montre comment faire une récursion de queue appropriée (en Lua, mais devrait également s'appliquer à Lisp) et pourquoi c'est mieux.
Vous voyez donc, lorsque vous effectuez un appel récursif comme:
Ce n'est pas récursif de queue parce que vous avez encore des choses à faire (ajouter 1) dans cette fonction après l'appel récursif. Si vous entrez un nombre très élevé, cela entraînera probablement un débordement de pile.
la source
En utilisant la récursivité régulière, chaque appel récursif pousse une autre entrée sur la pile d'appels. Lorsque la récursivité est terminée, l'application doit ensuite supprimer chaque entrée tout en bas.
Avec la récursivité de la queue, en fonction de la langue, le compilateur peut réduire la pile en une seule entrée, ce qui vous permet d'économiser de l'espace de pile ... Une grande requête récursive peut en fait provoquer un débordement de pile.
Fondamentalement, les récursions de queue peuvent être optimisées en itération.
la source
Le fichier jargon a ceci à dire sur la définition de la récursivité de la queue:
récursivité de la queue /n./
Si vous n'en avez pas déjà marre, voyez la récursivité de la queue.
la source
Au lieu de l'expliquer avec des mots, voici un exemple. Il s'agit d'une version Scheme de la fonction factorielle:
Voici une version de factorielle récursive:
Vous remarquerez dans la première version que l'appel récursif aux faits est introduit dans l'expression de multiplication, et donc l'état doit être enregistré sur la pile lors de l'appel récursif. Dans la version tail-recursive, aucune autre expression S n'attend la valeur de l'appel récursif, et comme il n'y a plus de travail à faire, l'état n'a pas besoin d'être enregistré sur la pile. En règle générale, les fonctions récursives de la queue Scheme utilisent un espace de pile constant.
la source
list-reverse
procédure de mutation liste-queue récursive-queue s'exécutera dans un espace de pile constant mais créera et augmentera une structure de données sur le tas. Une traversée d'arbre pourrait utiliser une pile simulée, dans un argument supplémentaire. etc.La récursivité de queue fait référence à l'appel récursif en dernier dans la dernière instruction logique de l'algorithme récursif.
Généralement en récursivité, vous avez un cas de base qui est ce qui arrête les appels récursifs et commence à faire apparaître la pile d'appels. Pour utiliser un exemple classique, bien que plus C-ish que Lisp, la fonction factorielle illustre la récursivité de la queue. L'appel récursif se produit après avoir vérifié l'état du cas de base.
L'appel initial à la factorielle serait
factorial(n)
oùfac=1
(valeur par défaut) et n est le nombre pour lequel la factorielle doit être calculée.la source
else
est l'étape que vous pourriez appeler un «cas de base», mais s'étend sur plusieurs lignes. Suis-je mal compris ou mon hypothèse est-elle correcte? La récursivité de la queue n'est bonne que pour une doublure?factorial
exemple est juste l'exemple simple classique, c'est tout.Cela signifie qu'au lieu de devoir pousser le pointeur d'instruction sur la pile, vous pouvez simplement sauter en haut d'une fonction récursive et continuer l'exécution. Cela permet aux fonctions de récurser indéfiniment sans déborder la pile.
J'ai écrit un article de blog sur le sujet, qui contient des exemples graphiques de l'apparence des cadres de pile.
la source
Voici un extrait de code rapide comparant deux fonctions. La première est la récursion traditionnelle pour trouver la factorielle d'un nombre donné. Le second utilise la récursivité de queue.
Très simple et intuitif à comprendre.
Un moyen simple de savoir si une fonction récursive est une récursive de queue consiste à renvoyer une valeur concrète dans le cas de base. Cela signifie qu'il ne renvoie pas 1 ou vrai ou quelque chose comme ça. Il retournera très probablement une variante de l'un des paramètres de la méthode.
Une autre façon est de savoir si l'appel récursif est exempt de tout ajout, arithmétique, modification, etc ... ce qui signifie que ce n'est qu'un appel récursif pur.
la source
La meilleure façon pour moi de comprendre
tail call recursion
est un cas spécial de récursivité où le dernier appel (ou le dernier appel) est la fonction elle-même.Comparaison des exemples fournis en Python:
^ RÉCURSION
^ RÉCURSION DE QUEUE
Comme vous pouvez le voir dans la version récursive générale, l'appel final dans le bloc de code est
x + recsum(x - 1)
. Donc, après avoir appelé larecsum
méthode, il y a une autre opération qui l'estx + ..
.Cependant, dans la version récursive de queue, l'appel final (ou l'appel de queue) dans le bloc de code est
tailrecsum(x - 1, running_total + x)
ce qui signifie que le dernier appel est fait à la méthode elle-même et aucune opération après cela.Ce point est important car la récursivité de la queue, comme on le voit ici, ne fait pas augmenter la mémoire car lorsque la machine virtuelle sous-jacente voit une fonction s'appelant dans une position de queue (la dernière expression à évaluer dans une fonction), elle élimine le cadre de pile actuel, qui est connu comme Tail Call Optimization (TCO).
ÉDITER
NB. Gardez à l'esprit que l'exemple ci-dessus est écrit en Python dont le runtime ne prend pas en charge TCO. Ceci est juste un exemple pour expliquer le point. TCO est pris en charge dans des langues comme Scheme, Haskell, etc.
la source
En Java, voici une implémentation récursive possible de la fonction Fibonacci:
Comparez cela avec l'implémentation récursive standard:
la source
iter
àacc
quanditer < (n-1)
.Je ne suis pas un programmeur Lisp, mais je pense que cela vous aidera.
Fondamentalement, c'est un style de programmation tel que l'appel récursif est la dernière chose que vous faites.
la source
Voici un exemple Common Lisp qui fait des factorielles en utilisant la récursion de queue. En raison de la nature sans pile, on pourrait effectuer des calculs factoriels incroyablement grands ...
Et puis pour le plaisir, vous pouvez essayer
(format nil "~R" (! 25))
la source
En bref, une récursion de queue a l'appel récursif comme dernière instruction de la fonction afin qu'elle n'ait pas à attendre l'appel récursif.
Il s'agit donc d'une récursion de queue, c'est-à-dire que N (x - 1, p * x) est la dernière instruction de la fonction où le compilateur est intelligent pour comprendre qu'il peut être optimisé en une boucle for (factorielle). Le deuxième paramètre p porte la valeur de produit intermédiaire.
C'est la façon non récursive d'écrire la fonction factorielle ci-dessus (bien que certains compilateurs C ++ puissent de toute façon l'optimiser).
mais ce n'est pas:
J'ai écrit un long article intitulé " Comprendre la récursivité de la queue - Visual Studio C ++ - Vue d'assemblage "
la source
voici une version Perl 5 de la
tailrecsum
fonction mentionnée plus haut.la source
Ceci est un extrait de Structure and Interpretation of Computer Programs about tail recursion.
la source
La fonction récursive est une fonction qui appelle par elle-même
Il permet aux programmeurs d'écrire des programmes efficaces en utilisant une quantité minimale de code .
L'inconvénient est qu'ils peuvent provoquer des boucles infinies et d'autres résultats inattendus s'ils ne sont pas écrits correctement .
Je vais expliquer à la fois la fonction récursive simple et la fonction récursive de queue
Pour écrire une fonction récursive simple
De l'exemple donné:
De l'exemple ci-dessus
Est le facteur décisif quand sortir de la boucle
Le traitement réel doit-il être effectué
Permettez-moi de rompre la tâche une par une pour une compréhension facile.
Voyons ce qui se passe en interne si je cours
fact(4)
If
la boucle échoue alors elle passe enelse
boucle pour revenir4 * fact(3)
Dans la mémoire de la pile, nous avons
4 * fact(3)
Remplaçant n = 3
If
la boucle échoue donc elle passe enelse
boucledonc ça revient
3 * fact(2)
N'oubliez pas que nous avons appelé `` `` 4 * fact (3) ''
La sortie pour
fact(3) = 3 * fact(2)
Jusqu'à présent, la pile a
4 * fact(3) = 4 * 3 * fact(2)
Dans la mémoire de la pile, nous avons
4 * 3 * fact(2)
Remplaçant n = 2
If
la boucle échoue donc elle passe enelse
boucledonc ça revient
2 * fact(1)
N'oubliez pas que nous avons appelé
4 * 3 * fact(2)
La sortie pour
fact(2) = 2 * fact(1)
Jusqu'à présent, la pile a
4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)
Dans la mémoire de la pile, nous avons
4 * 3 * 2 * fact(1)
Remplaçant n = 1
If
la boucle est vraiedonc ça revient
1
N'oubliez pas que nous avons appelé
4 * 3 * 2 * fact(1)
La sortie pour
fact(1) = 1
Jusqu'à présent, la pile a
4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1
Enfin, le résultat de fait (4) = 4 * 3 * 2 * 1 = 24
La récursivité de la queue serait
If
la boucle échoue alors elle passe enelse
boucle pour revenirfact(3, 4)
Dans la mémoire de la pile, nous avons
fact(3, 4)
Remplaçant n = 3
If
la boucle échoue donc elle passe enelse
boucledonc ça revient
fact(2, 12)
Dans la mémoire de la pile, nous avons
fact(2, 12)
Remplaçant n = 2
If
la boucle échoue donc elle passe enelse
boucledonc ça revient
fact(1, 24)
Dans la mémoire de la pile, nous avons
fact(1, 24)
Remplaçant n = 1
If
la boucle est vraiedonc ça revient
running_total
La sortie pour
running_total = 24
Enfin, le résultat de fait (4,1) = 24
la source
La récursivité de la queue est la vie que vous vivez en ce moment. Vous recyclez constamment le même cadre de pile, encore et encore, car il n'y a aucune raison ou moyen de revenir à un cadre "précédent". Le passé est révolu pour qu'il puisse être jeté. Vous obtenez une image, vous vous déplaçant à jamais vers l'avenir, jusqu'à ce que votre processus meure inévitablement.
L'analogie tombe en panne lorsque vous considérez que certains processus peuvent utiliser des trames supplémentaires, mais sont toujours considérés comme récursifs si la pile ne croît pas à l'infini.
la source
Considérons le problème du calcul factoriel d'un nombre.
Une approche simple serait:
Supposons que vous appeliez factorielle (4). L'arbre de récursivité serait:
La profondeur de récursivité maximale dans le cas ci-dessus est O (n).
Cependant, considérez l'exemple suivant:
L'arbre de récursivité pour factTail (4) serait:
Ici aussi, la profondeur de récursivité maximale est O (n) mais aucun des appels n'ajoute de variable supplémentaire à la pile. Par conséquent, le compilateur peut supprimer une pile.
la source
La récursion de queue est assez rapide par rapport à la récursivité normale. C'est rapide car la sortie de l'appel des ancêtres ne sera pas écrite dans la pile pour garder la trace. Mais dans la récursivité normale, tous les ancêtres appellent la sortie écrite dans la pile pour garder la trace.
la source
Une fonction récursive de queue est une fonction récursive où la dernière opération qu'elle effectue avant de retourner est de faire l'appel de la fonction récursive. Autrement dit, la valeur de retour de l'appel de fonction récursive est immédiatement renvoyée. Par exemple, votre code ressemblerait à ceci:
Les compilateurs et les interprètes qui implémentent l' optimisation des appels de queue ou l' élimination des appels de queue peuvent optimiser le code récursif pour éviter les débordements de pile. Si votre compilateur ou interprète n'implémente pas l'optimisation des appels de queue (comme l'interpréteur CPython), il n'y a aucun avantage supplémentaire à écrire votre code de cette façon.
Par exemple, il s'agit d'une fonction factorielle récursive standard en Python:
Et ceci est une version récursive de l'appel de queue de la fonction factorielle:
(Notez que même s'il s'agit de code Python, l'interpréteur CPython ne fait pas d'optimisation des appels de queue, donc organiser votre code comme celui-ci ne confère aucun avantage à l'exécution.)
Vous devrez peut-être rendre votre code un peu plus illisible pour utiliser l'optimisation des appels de queue, comme le montre l'exemple factoriel. (Par exemple, le scénario de base est maintenant un peu peu intuitif et le
accumulator
paramètre est effectivement utilisé comme une sorte de variable globale.)Mais l'avantage de l'optimisation des appels de queue est qu'elle empêche les erreurs de débordement de pile. (Je noterai que vous pouvez obtenir ce même avantage en utilisant un algorithme itératif au lieu d'un algorithme récursif.)
Les débordements de pile sont provoqués lorsque la pile d'appels a reçu trop d'objets frame. Un objet frame est poussé sur la pile d'appels lorsqu'une fonction est appelée et sauté hors de la pile d'appels lorsque la fonction revient. Les objets Frame contiennent des informations telles que les variables locales et la ligne de code à retourner lorsque la fonction revient.
Si votre fonction récursive effectue trop d'appels récursifs sans retour, la pile d'appels peut dépasser sa limite d'objet de trame. (Le nombre varie selon la plate-forme; en Python, il s'agit de 1000 objets de trame par défaut.) Cela provoque une erreur de dépassement de pile . (Hé, c'est de là que vient le nom de ce site!)
Cependant, si la dernière chose que fait votre fonction récursive est de faire l'appel récursif et de renvoyer sa valeur de retour, il n'y a aucune raison pour qu'elle garde l'objet frame actuel pour rester dans la pile des appels. Après tout, s'il n'y a pas de code après l'appel de fonction récursive, il n'y a aucune raison de s'accrocher aux variables locales de l'objet cadre actuel. Nous pouvons donc nous débarrasser de l'objet cadre actuel immédiatement plutôt que de le conserver dans la pile des appels. Le résultat final est que votre pile d'appels n'augmente pas en taille et ne peut donc pas déborder.
Un compilateur ou un interpréteur doit avoir l'optimisation des appels de queue comme une fonctionnalité pour pouvoir reconnaître quand l'optimisation des appels de queue peut être appliquée. Même alors, vous pouvez avoir réorganisé le code dans votre fonction récursive pour utiliser l'optimisation des appels de queue, et c'est à vous de décider si cette diminution potentielle de la lisibilité vaut l'optimisation.
la source
Pour comprendre certaines des principales différences entre la récursivité d'appel de queue et la récursion sans appel de queue, nous pouvons explorer les implémentations .NET de ces techniques.
Voici un article avec quelques exemples en C #, F # et C ++ \ CLI: Adventures in Tail Recursion en C #, F # et C ++ \ CLI .
C # n'optimise pas pour la récursivité d'appel de queue alors que F # le fait.
Les différences de principe impliquent des boucles par rapport au calcul Lambda. C # est conçu avec des boucles à l'esprit tandis que F # est construit à partir des principes du calcul Lambda. Pour un très bon (et gratuit) livre sur les principes du calcul lambda, voir Structure and Interpretation of Computer Programs, par Abelson, Sussman et Sussman .
Concernant les appels de queue en F #, pour un très bon article d'introduction, voir Introduction détaillée aux appels de queue en F # . Enfin, voici un article qui couvre la différence entre la récursion non-queue et la récursivité appel-queue (en F #): récursion-queue vs récursion non-queue en F sharp .
Si vous souhaitez en savoir plus sur certaines des différences de conception de la récursivité des appels de queue entre C # et F #, consultez Génération de l'opcode Tail-Call en C # et F # .
Si vous vous souciez suffisamment de vouloir savoir quelles conditions empêchent le compilateur C # d'effectuer des optimisations d'appel de fin, consultez cet article: Conditions d'appel de fin JIT CLR .
la source
Il existe deux types de récursions de base: la récursion de tête et la récursion de queue.
Tiré de ce post super génial. Veuillez envisager de le lire.
la source
La récursivité signifie une fonction qui s'appelle elle-même. Par exemple:
Tail-Recursion signifie la récursion qui conclut la fonction:
Vous voyez, la dernière chose que la fonction non terminée (procédure, dans le jargon du schéma) fait est de s'appeler. Un autre exemple (plus utile) est:
Dans la procédure d'aide, la DERNIÈRE chose qu'elle fait si la gauche n'est pas nulle est de s'appeler (après quelque chose contre et quelque chose cdr). Voici essentiellement comment mapper une liste.
La récursivité de queue a un grand avantage que l'interpréteur (ou le compilateur, dépendant de la langue et du fournisseur) peut l'optimiser et le transformer en quelque chose d'équivalent à une boucle while. En fait, dans la tradition de Scheme, la plupart des boucles "for" et "while" se font de manière récursive (il n'y en a pas pour et pendant, pour autant que je sache).
la source
Cette question a beaucoup de bonnes réponses ... mais je ne peux pas m'empêcher de donner un coup de pouce avec une alternative sur la façon de définir la "récursivité de la queue", ou au moins "la récursion de la queue appropriée". A savoir: faut-il la regarder comme une propriété d'une expression particulière dans un programme? Ou faut-il la considérer comme une propriété d'une implémentation d'un langage de programmation ?
Pour en savoir plus sur ce dernier point de vue, il existe un article classique de Will Clinger, "Proper Tail Recursion and Space Efficiency" (PLDI 1998), qui définit la "bonne queue récursivité" comme une propriété d'une implémentation de langage de programmation. La définition est construite pour permettre d'ignorer les détails d'implémentation (par exemple, si la pile d'appels est réellement représentée via la pile d'exécution ou via une liste liée de trames allouée par segment).
Pour ce faire, il utilise une analyse asymptotique: non pas du temps d'exécution du programme comme on le voit habituellement, mais plutôt de l'utilisation de l'espace du programme . De cette façon, l'utilisation de l'espace d'une liste liée allouée par segment de mémoire par rapport à une pile d'appels d'exécution finit par être équivalente asymptotiquement; donc on arrive à ignorer ce détail d'implémentation du langage de programmation (un détail qui importe certainement un peu en pratique, mais peut brouiller les eaux un peu quand on essaie de déterminer si une implémentation donnée satisfait à l'exigence d'être "propriété récursive") )
Le document mérite une étude approfondie pour un certain nombre de raisons:
Il donne une définition inductive des expressions de queue et des appels de queue d'un programme. (Une telle définition, et pourquoi de tels appels sont importants, semble faire l'objet de la plupart des autres réponses données ici.)
Voici ces définitions, juste pour donner un aperçu du texte:
(Un appel récursif de queue, ou comme le dit l'article, "l'appel de self-tail" est un cas spécial d'un appel de queue où la procédure est invoquée elle-même.)
Il fournit des définitions formelles pour six "machines" différentes pour évaluer le schéma de base, où chaque machine a le même comportement observable à l' exception de la classe de complexité d'espace asymptotique dans laquelle chacune se trouve.
Par exemple, après avoir donné des définitions pour les machines avec respectivement: 1. la gestion de la mémoire basée sur la pile, 2. le garbage collection mais pas d'appels de queue, 3. le garbage collection et les appels de queue, le papier continue avec des stratégies de gestion du stockage encore plus avancées, telles que 4. "evlis tail recursion", où l'environnement n'a pas besoin d'être préservé tout au long de l'évaluation du dernier argument de sous-expression dans un appel de queue, 5. réduire l'environnement d'une fermeture aux seules variables libres de cette fermeture, et 6. la sémantique dite «sûre pour l'espace» telle que définie par Appel et Shao .
Afin de prouver que les machines appartiennent en fait à six classes de complexité d'espace distinctes, l'article, pour chaque paire de machines comparées, fournit des exemples concrets de programmes qui exposeront l'explosion d'espace asymptotique sur une machine mais pas sur l'autre.
(En lisant ma réponse maintenant, je ne sais pas si j'ai réussi à saisir les points cruciaux du document Clinger . Mais, hélas, je ne peux pas consacrer plus de temps à l'élaboration de cette réponse pour le moment.)
la source
Beaucoup de gens ont déjà expliqué la récursivité ici. Je voudrais citer quelques réflexions sur certains avantages que la récursivité donne du livre "Concurrency in .NET, Modern patterns of concurrent and parallel programming" de Riccardo Terrell:
Voici également quelques notes intéressantes du même livre sur la récursivité de la queue:
la source