Qu’est-ce que la récursion de la queue?

Tout en commençant à apprendre le lisp, j’ai rencontré le terme récursif . Qu’est-ce que cela signifie exactement?

Considérons une fonction simple qui ajoute les N premiers entiers. (ex: sum(5) = 1 + 2 + 3 + 4 + 5 = 15 ).

Voici une implémentation JavaScript simple qui utilise la récursivité:

 function recsum(x) { if (x===1) { return x; } else { return x + recsum(x-1); } } 

Si vous recsum(5) , recsum(5) ce que l’interpréteur JavaScript évaluerait:

 recsum(5) 5 + recsum(4) 5 + (4 + recsum(3)) 5 + (4 + (3 + recsum(2))) 5 + (4 + (3 + (2 + recsum(1)))) 5 + (4 + (3 + (2 + 1))) 15 

Notez comment chaque appel récursif doit se terminer avant que l’interpréteur JavaScript commence à effectuer le travail de calcul de la sum.

Voici une version récursive de la même fonction:

 function tailrecsum(x, running_total=0) { if (x===0) { return running_total; } else { return tailrecsum(x-1, running_total+x); } } 

Voici la suite des événements qui se produiraient si vous tailrecsum(5) , (qui serait effectivement tailrecsum(5, 0) , à cause du second argument par défaut).

 tailrecsum(5, 0) tailrecsum(4, 5) tailrecsum(3, 9) tailrecsum(2, 12) tailrecsum(1, 14) tailrecsum(0, 15) 15 

Dans le cas récursif, à chaque évaluation de l’appel récursif, le running_total est mis à jour.

Remarque: La réponse originale utilisait des exemples de Python. Ceux-ci ont été changés en JavaScript, car les interpréteurs JavaScript modernes prennent en charge l’ optimisation des appels de queue, contrairement aux interpréteurs Python.

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.

En récursivité , 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. Cela se traduit par la dernière déclaration sous la forme de (return (recursive-function params)) . Fondamentalement, la valeur de retour d’une étape récursive donnée est la même que la valeur de retour de l’appel récursif suivant .

La conséquence de ceci est qu’une fois que vous êtes prêt à effectuer votre prochaine étape récursive, vous n’avez plus besoin du cadre de stack actuel. Cela permet une certaine optimisation. En fait, avec un compilateur correctement écrit, vous ne devriez jamais avoir un snicker de débordement de stack avec un appel récursif de queue. Réutilisez simplement le cadre de stack actuel pour l’étape suivante récursive. Je suis sûr que Lisp fait ça.

Un point important est que la récursion de la queue est essentiellement équivalente à la boucle. Ce n’est pas seulement une question d’optimisation du compilateur, mais un fait fondamental de l’expressivité. Cela va dans les deux sens: vous pouvez prendre n’importe quelle boucle du formulaire

 while(E) { S }; return Q 

E et Q sont des expressions et S est une suite d’instructions, et la transforme en une fonction récursive de queue

 f() = if E then { S; return f() } else { return Q } 

Bien entendu, E , S et Q doivent être définis pour calculer une valeur intéressante sur certaines variables. Par exemple, la fonction de bouclage

 sum(n) { int i = 1, k = 0; while( i <= n ) { k += i; ++i; } return k; } 

est équivalent à la ou aux fonctions récursives

 sum_aux(n,i,k) { if( i <= n ) { return sum_aux(n,i+1,k+i); } else { return k; } } sum(n) { return sum_aux(n,1,0); } 

(Ce "wrapping" de la fonction récursive avec une fonction avec moins de parameters est un idiome fonctionnel commun.)

Cet extrait du livre Programming in Lua montre comment faire une récursion de queue correcte (dans Lua, mais devrait aussi s’appliquer à Lisp) et pourquoi c’est mieux.

Un appel de queue [récursivité de la queue] est une sorte de goto habillé comme un appel. Un appel de queue se produit lorsqu’une fonction en appelle une autre comme dernière action, elle n’a donc rien d’autre à faire. Par exemple, dans le code suivant, l’appel à g est un appel de fin:

 function f (x) return g(x) end 

Après que f appelle g , il n’a plus rien à faire. Dans de telles situations, le programme n’a pas besoin de retourner à la fonction d’appel lorsque la fonction appelée se termine. Par conséquent, après l’appel de fin, le programme n’a pas besoin de conserver d’informations sur la fonction d’appel dans la stack. …

Étant donné qu’un appel de fin approprié n’utilise aucun espace de stack, le nombre d’appels de queue “nesteds” qu’un programme peut effectuer est illimité. Par exemple, on peut appeler la fonction suivante avec n’importe quel nombre comme argument; il ne débordera jamais la stack:

 function foo (n) if n > 0 then return foo(n - 1) end end 

… Comme je l’ai dit plus tôt, un appel de queue est une sorte de goto. En tant que tel, une application très utile des appels de queue appropriés dans Lua est pour la programmation des machines à états. De telles applications peuvent représenter chaque état par une fonction; changer d’état, c’est aller (ou appeler) une fonction spécifique. À titre d’exemple, considérons un simple jeu de labyrinthe. Le labyrinthe comprend plusieurs salles, chacune pouvant accueillir jusqu’à quatre portes: nord, sud, est et ouest. À chaque étape, l’utilisateur entre dans une direction de mouvement. S’il y a une porte dans cette direction, l’utilisateur se rend dans la pièce correspondante; sinon, le programme imprime un avertissement. Le but est de passer d’une première salle à une dernière salle.

Ce jeu est une machine à états typique, où la pièce actuelle est l’état. Nous pouvons implémenter un tel labyrinthe avec une fonction pour chaque pièce. Nous utilisons les appels de queue pour passer d’une pièce à l’autre. Un petit labyrinthe de quatre pièces pourrait ressembler à ceci:

 function room1 () local move = io.read() if move == "south" then return room3() elseif move == "east" then return room2() else print("invalid move") return room1() -- stay in the same room end end function room2 () local move = io.read() if move == "south" then return room4() elseif move == "west" then return room1() else print("invalid move") return room2() end end function room3 () local move = io.read() if move == "north" then return room1() elseif move == "east" then return room4() else print("invalid move") return room3() end end function room4 () print("congratulations!") end 

Donc, vous voyez, quand vous faites un appel récursif comme:

 function x(n) if n==0 then return 0 n= n-2 return x(n) + 1 end 

Ceci n’est pas récursif car vous avez encore des choses à faire (append 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 stack.

En utilisant la récursivité régulière, chaque appel récursif pousse une autre entrée sur la stack d’appels. Lorsque la récursivité est terminée, l’application doit ensuite supprimer chaque entrée.

Avec la récursion de la queue, le compilateur est capable de réduire la stack à une entrée, ce qui vous permet d’économiser de la stack … Une requête récursive volumineuse peut en réalité provoquer un débordement de stack.

Fondamentalement, les récurrences de queue peuvent être optimisées en itération.

Au lieu de l’expliquer par des mots, voici un exemple. Ceci est une version Scheme de la fonction factorielle:

 (define (factorial x) (if (= x 0) 1 (* x (factorial (- x 1))))) 

Voici une version de factorielle qui est récursive:

 (define factorial (letrec ((fact (lambda (x accum) (if (= x 0) accum (fact (- x 1) (* accum x)))))) (lambda (x) (fact x 1)))) 

Vous remarquerez dans la première version que l’appel récursif à fact est introduit dans l’expression de multiplication et que, par conséquent, l’état doit être sauvegardé sur la stack lors de l’appel récursif. Dans la version récursive, il n’y a pas d’autre expression S en attente de la valeur de l’appel récursif, et comme il n’y a plus de travail à faire, il n’est pas nécessaire d’enregistrer l’état sur la stack. En règle générale, les fonctions Scheme tail-recursive utilisent un espace de stack constant.

Le fichier de jargon dit ceci à propos de la définition de la récursion de la queue:

récursion de queue /n./

Si vous n’en avez pas encore assez, voyez la récursion de la queue.

La récursion de la queue fait référence à l’appel récursif étant le 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 arrête les appels récursifs et commence à ouvrir la stack 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 vérification de la condition de base.

 factorial(x, fac) { if (x == 1) return fac; else return factorial(x-1, x*fac); } 

Notez que l’appel initial à factorial doit être factoriel (n, 1) où n est le nombre pour lequel la factorielle doit être calculée.

Cela signifie que plutôt que d’avoir besoin de pousser le pointeur d’instruction sur la stack, vous pouvez simplement sauter en haut d’une fonction récursive et continuer l’exécution. Cela permet aux fonctions de se déclencher indéfiniment sans déborder la stack.

J’ai écrit un article de blog sur le sujet, qui contient des exemples graphiques de ce à quoi ressemblent les frameworks de stack.

Voici un extrait de code rapide comparant deux fonctions. La première est la récursivité traditionnelle pour trouver la factorielle d’un nombre donné. La seconde utilise la récursion de la queue.

Très simple et intuitif à comprendre.

Un moyen facile de savoir si une fonction récursive est récursive est si elle renvoie une valeur concrète dans le cas de base. Ce qui signifie qu’il ne retourne pas 1 ou vrai ou quelque chose comme ça. Il renverra probablement plus tard une variante de l’un des parameters de la méthode.

Une autre façon de le savoir est de savoir si l’appel récursif est libre de toute addition, arithmétique, modification, etc. Ce qui signifie que ce n’est rien d’autre qu’un pur appel récursif.

 public static int factorial(int mynumber) { if (mynumber == 1) { return 1; } else { return mynumber * factorial(--mynumber); } } public static int tail_factorial(int mynumber, int sofar) { if (mynumber == 1) { return sofar; } else { return tail_factorial(--mynumber, sofar * mynumber); } } 

En Java, voici une implémentation récursive possible de la fonction Fibonacci:

 public int tailRecursive(final int n) { if (n <= 2) return 1; return tailRecursiveAux(n, 1, 1); } private int tailRecursiveAux(int n, int iter, int acc) { if (iter == n) return acc; return tailRecursiveAux(n, ++iter, acc + iter); } 

Contrastez ceci avec l'implémentation récursive standard:

 public int recursive(final int n) { if (n <= 2) return 1; return recursive(n - 1) + recursive(n - 2); } 

La meilleure façon pour moi de comprendre la tail call recursion est: un cas particulier de récurrence où le dernier appel (ou l’appel de fin) est la fonction elle-même.

En comparant les exemples fournis dans Python:

 def recsum(x): if x == 1: return x else: return x + recsum(x - 1) 

^ RECURSION

 def tailrecsum(x, running_total=0): if x == 0: return running_total else: return tailrecsum(x - 1, running_total + x) 

^ 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é la méthode recsum , il y a une autre opération qui est x + ..

Cependant, dans la version récursive de la queue, l’appel final (ou l’appel de fin) dans le bloc de code est tailrecsum(x - 1, running_total + x) ce qui signifie que le dernier appel est effectué.

Ce point est important car la récursion de la queue telle qu’elle est vue ici ne fait pas croître la mémoire car lorsque la machine virtuelle sous-jacente voit une fonction s’appeler elle-même en position finale (dernière expression à évaluer) est connu sous le nom de TCO (Tail Call Optimization).

MODIFIER

NB Gardez à l’esprit que l’exemple ci-dessus est écrit en Python dont l’exécution ne prend pas en charge TCO. Ceci est juste un exemple pour expliquer le point. TCO est supporté dans des langages comme Scheme, Haskell etc.

Voici un exemple de Lisp commun qui effectue des factorielles en utilisant la récursion de la queue. En raison de la nature sans stack, on peut effectuer des calculs factoriels incroyablement grands …

 (defun ! (n &optional (product 1)) (if (zerop n) product (! (1- n) (* product n)))) 

Et puis, pour vous amuser, vous pouvez essayer (format nil "~R" (! 25))

Voici une version de Perl 5 de la fonction tailrecsum mentionnée plus haut.

 sub tail_rec_sum($;$){ my( $x,$running_total ) = (@_,0); return $running_total unless $x; @_ = ($x-1,$running_total+$x); goto &tail_rec_sum; # throw away current stack frame } 

En bref, une récursion de la queue a l’appel récursif comme dernière instruction de la fonction, de sorte qu’elle n’a 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 habile à comprendre qu’il peut être optimisé pour une for-loop (factorielle). Le second paramètre p porte la valeur du produit intermédiaire.

 function N(x, p) { return x == 1 ? p : N(x - 1, p * x); } 

C’est la manière non récursive d’écrire la fonction factorielle ci-dessus (bien que certains compilateurs C ++ puissent être capables de l’optimiser de toute façon).

 function N(x) { return x == 1 ? 1 : x * N(x - 1); } 

mais ce n’est pas:

 function F(x) { if (x == 1) return 0; if (x == 2) return 1; return F(x - 1) + F(x - 2); } 

J’ai écrit un long post intitulé ” Comprendre la récursion de la queue – Visual Studio C ++ – Vue Assemblage ”

entrer la description de l'image ici

Je ne suis pas un programmeur Lisp, mais je pense que cela aidera.

Fondamentalement, c’est un style de programmation tel que l’appel récursif est la dernière chose que vous faites.

Pour comprendre certaines des différences fondamentales entre la récursion d’appel 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: Aventures dans la récursion de queue en C #, F # et C ++ \ CLI .

C # n’optimise pas pour la récursion 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 en tête alors que F # est construit à partir des principes du calcul Lambda. Pour un très bon livre (gratuit) sur les principes du calcul lambda, voir: Structure et interprétation des programmes informatiques, par Abelson, Sussman et Sussman .

En ce qui concerne les appels de queue dans F #, pour un très bon article d’introduction, voir: Introduction détaillée aux appels de queue dans F # . Enfin, voici un article qui couvre la différence entre la récursion hors queue et la récursion d’appel de queue (en F #): récursivité de la queue par rapport à la récursion sans queue dans F sharp .

Si vous souhaitez en savoir plus sur certaines différences de conception de la récursion d’appel entre C # et F #, voir: Génération d’un code d’opération d’appel en C # et F # .

Si vous voulez savoir quelles sont les conditions qui empêchent le compilateur C # d’effectuer des optimisations de type «tail-call», consultez cet article: Conditions d’appel du JIT CLR .

Ceci est un extrait de Structure et interprétation de programmes informatiques sur la récursion de la queue.

En contraste avec l’itération et la récursivité, nous devons faire attention à ne pas confondre la notion de processus récursif avec la notion de procédure récursive. Lorsque nous décrivons une procédure comme récursive, nous faisons référence au fait syntaxique que la définition de procédure fait référence (directement ou indirectement) à la procédure elle-même. Mais lorsque nous décrivons un processus comme suit un modèle qui est, par exemple, linéaire récursif, nous parlons de l’évolution du processus, et non de la syntaxe de l’écriture d’une procédure. Il peut sembler troublant que nous nous référions à une procédure récursive telle que fact-iter, générant un processus itératif. Cependant, le processus est vraiment itératif: son état est complètement capturé par ses trois variables d’état, et un interpréteur n’a besoin de suivre que trois variables pour exécuter le processus.

Une des raisons pour lesquelles la distinction entre processus et procédure peut être déroutante est que la plupart des implémentations de langages communs (y compris Ada, Pascal et C) sont conçues de telle manière que l’interprétation de toute procédure récursive consum une quantité de mémoire croissante. nombre d’appels de procédure, même lorsque le processus décrit est, en principe, itératif. En conséquence, ces langages ne peuvent décrire les processus itératifs qu’en ayant recours à des «constructions en boucle» spécifiques, telles que do, repeat, until, for et while. La mise en œuvre de Scheme ne partage pas ce défaut. Il exécutera un processus itératif dans un espace constant, même si le processus itératif est décrit par une procédure récursive. Une implémentation avec cette propriété s’appelle tail-recursive. Avec une implémentation récursive, l’itération peut être exprimée à l’aide du mécanisme d’appel de procédure ordinaire, de sorte que les constructions d’itération spéciales ne sont utiles que comme sucre syntaxique.

La récursion de la queue est la vie que vous vivez en ce moment. Vous recyclez constamment le même cadre de stack, encore et encore, car il n’ya aucune raison ou moyen de revenir à un cadre «précédent». Le passé est terminé et peut donc être rejeté. Vous obtenez une image, toujours dans le futur, jusqu’à ce que votre processus meure inévitablement.

L’analogie disparaît lorsque vous considérez que certains processus peuvent utiliser des trames supplémentaires mais sont toujours considérés comme récursifs si la stack ne se développe pas à l’infini.

La récursivité signifie une fonction appelant elle-même. Par exemple:

 (define (un-ended name) (un-ended 'me) (print "How can I get here?")) 

Tail-Recursion désigne la récursivité qui termine la fonction:

 (define (un-ended name) (print "hello") (un-ended 'me)) 

Voir, la dernière chose que la fonction non terminée (procédure, dans le jargon Scheme) fait est de s’appeler elle-même. Un autre exemple (plus utile) est:

 (define (map lst op) (define (helper done left) (if (nil? left) done (helper (cons (op (car left)) done) (cdr left)))) (reverse (helper '() lst))) 

Dans la procédure d’aide, la dernière chose qu’elle fait si elle n’est pas nulle, c’est de s’appeler elle-même (après quelque chose et cdr quelque chose). C’est essentiellement la façon dont vous mappez une liste.

La récursivité présente un grand avantage: l’interpolateur (ou le compilateur, dépendant du langage 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 (à ma connaissance, il n’y en a pas pour et pendant).

Cette question a beaucoup de bonnes réponses … mais je ne peux pas m’empêcher de jouer avec une autre approche sur la façon de définir la “récursion de la queue”, ou du moins la “récursion de la queue”. A savoir: faut-il le regarder comme une propriété d’une expression particulière dans un programme? Ou faut-il le considérer comme une propriété d’une implémentation d’un langage de programmation ?

Pour en savoir plus sur ce dernier sharepoint vue, il existe un article classique de Will Clinger intitulé “Propursion de la récursion et efficacité de l’espace” (PLDI 1998), qui définit la “récursion de la queue” comme 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 stack d’appels est réellement représentée via la stack d’exécution ou via une liste de liens liée allouée au tas).

Pour ce faire, il utilise une parsing asymptotique: 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 d’espace d’une liste chaînée allouée en tas par rapport à une stack d’appels en cours d’exécution finit par être asymptotiquement équivalente; on peut donc ignorer les détails de l’implémentation du langage de programmation (un détail qui a certes beaucoup d’importance dans la pratique, mais qui peut brouiller un peu lorsqu’on essaie de déterminer si une implémentation donnée satisfait à l’exigence d’être “propriété tail 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 fin d’un programme. (Une telle définition, et pourquoi ces appels sont importants, semble faire l’object de la plupart des autres réponses données ici.)

    Voici ces définitions, juste pour donner une idée du texte:

    Définition 1 Les expressions de queue d’un programme écrit dans Core Scheme sont définies de manière inductive comme suit.

    1. Le corps d’une expression lambda est une expression de queue
    2. Si (if E0 E1 E2) est une expression de queue, alors les deux E1 et E2 sont des expressions de queue.
    3. Rien d’autre n’est une expression de queue.

    Définition 2 Un appel de fin est une expression de queue qui est un appel de procédure.

(un appel récursif à la queue, ou comme le dit l’article, “appel à la queue” est un cas particulier d’un appel à la 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, chaque machine ayant le même comportement observable, à l’ exception de la classe de complexité d’espace asymptotique dans laquelle elles se trouvent.

    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 stack, 2. la récupération de la mémoire mais pas les appels de queue, 3. la récupération de place et les appels de fin, 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é lors de l’évaluation du dernier argument de sous-expression dans un appel de queue, 5. réduisant l’environnement d’une fermeture aux seules variables libres de cette fermeture, et 6. Sémantique dite “sûre pour l’espace” telle que définie par Appel et Shao .

  • Afin de prouver que les machines appartiennent en réalité à six classes de complexité d’espace distinctes, le papier, pour chaque paire de machines comparées, fournit des exemples concrets de programmes qui exposeront les explosions d’espace asymptotiques sur une machine mais pas sur l’autre.


(En relisant ma réponse maintenant, je ne sais pas si je parviens à capturer les points cruciaux de l’ article de Clinger . Mais, hélas, je ne peux pas consacrer plus de temps à développer cette réponse maintenant.)

Une récursion de queue est une fonction récursive où la fonction s’appelle à la fin (“tail”) de la fonction dans laquelle aucun calcul n’est effectué après le retour de l’appel récursif. De nombreux compilateurs optimisent pour transformer un appel récursif en appel récursif ou itératif.

Considérons le problème du calcul factoriel d’un nombre.

Une approche simple serait:

  factorial(n): if n==0 then 1 else n*factorial(n-1) 

Supposons que vous appeliez factorial (4). L’arbre de récursivité serait:

  factorial(4) / \ 4 factorial(3) / \ 3 factorial(2) / \ 2 factorial(1) / \ 1 factorial(0) \ 1 

La profondeur de récursivité maximale dans le cas ci-dessus est O (n).

Toutefois, prenons l’exemple suivant:

 factAux(m,n): if n==0 then m; else factAux(m*n,n-1); factTail(n): return factAux(1,n); 

L’arbre de récurrence pour factTail (4) serait:

 factTail(4) | factAux(1,4) | factAux(4,3) | factAux(12,2) | factAux(24,1) | factAux(24,0) | 24 

Ici aussi, la profondeur de récursivité maximale est O (n), mais aucun des appels ne ajoute de variable supplémentaire à la stack. Le compilateur peut donc supprimer une stack.

Il existe deux types de récurrences: la récursion de la tête et la récursion de la queue.

Dans la récursion principale , une fonction effectue son appel récursif, puis effectue d’autres calculs, en utilisant par exemple le résultat de l’appel récursif.

Dans une fonction récursive de queue , tous les calculs ont lieu en premier et l’appel récursif est la dernière chose qui se produit.

Tiré de ce post super génial. S’il vous plaît envisager de le lire.