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

dans recursion traditionnelle , le modèle typique est que vous effectuez vos appels récursifs d'abord, puis vous prenez la valeur de retour de l'appel récursif et calculer le résultat. De cette façon, vous n'obtenez pas le résultat de votre calcul tant que vous n'êtes pas revenu de chaque appel récursif.

dans retail recursion , vous effectuez d'abord vos calculs, puis vous exécutez l'appel récursif, en passant les résultats de votre étape actuelle à la prochaine étape récursive. Il en résulte que la dernière mention est sous la forme de (return (recursive-function params)) . fondamentalement, la valeur de retour d'un pas récursif donné 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 une bonne compilateur écrit, vous ne devriez jamais avoir un débordement de pile snicker avec un appel récursif de queue. Simplement réutiliser la pile en cours pour la prochaine étape récursive. Je suis sûr que Lisp.

un point important est que la recursion de la queue est essentiellement équivalente à une boucle. Ce n'est pas juste 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 de la forme

while(E) { S }; return Q

où E et Q sont des expressions et S est une séquence d'énoncés, et la transformer en une fonction récursive de queue

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

bien sûr, E , S , et Q doivent être définis pour calculer une valeur intéressante sur certaines variables. Par exemple, la fonction de boucle

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

est équivalent à la queue-fonction récursive(s)

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 "enveloppement" de la fonction queue-récursive avec une fonction avec moins de paramètres est un idiome fonctionnel courant.)

cet extrait du livre programmation en Lua montre comment faire une bonne récursion de queue (en Lua, mais devrait s'appliquer à Lisp aussi) et pourquoi il est mieux.

Un queue d'appel [la récursivité tail] est une sorte de goto habillé comme un appel. Un appel de queue se produit quand un fonction appelle un autre comme son dernier action, donc il n'a rien d'autre à faire. Par exemple, dans le code suivant, l'appel à g est un appel de queue:

function f (x)
  return g(x)
end

après f appelle g , il n'y a rien d'autre faire. Dans de telles situations, le programme n'a pas besoin de retourner à l'appelant la fonction lorsque la fonction appelée fourchues. Par conséquent, après l'appel de la queue, le programme n'a pas besoin de garder tout informations sur la fonction d'appel dans la pile. ...

parce qu'un appel de queue approprié utilise non l'espace de pile, il n'y a pas de limite sur le nombre d'appels de queue "imbriqués" qu'un le programme peut faire. Par exemple, nous pouvons appeler la fonction suivante avec tout nombre comme argument; il ne sera jamais débordement de la pile:

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 un une sorte de goto. En tant que tel, un très utile application d'appels de queue appropriés Lua est pour la programmation des machines d'état. Ces applications peuvent représenter de l'état par une fonction; pour changer l'état est de aller à (ou à l'appel) fonction. Comme un exemple, laissez-nous considérons un simple jeu de labyrinthe. Labyrinthe dispose de plusieurs chambres, chacune avec quatre portes: nord, sud, est, et ouest. À chaque étape, l'utilisateur entre un la direction du mouvement. Si il y a une porte dans ce sens, l'utilisateur passe à la pièce correspondante; sinon, l' le programme affiche un avertissement. L'objectif est pour aller d'une première salle de finale chambre.

ce jeu est une machine d'état typique, où la salle de cours est l'état. Nous pouvons mettre en œuvre un tel labyrinthe avec un fonction pour chaque chambre. Nous utilisons la queue les appels pour passer d'une chambre à 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

ainsi 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

ce n'est pas récursif de queue parce que vous avez encore des choses à faire (ajouter 1) dans cette fonction après que l'appel récursif est fait. Si vous avez entrée un nombre très élevé causera probablement un débordement de la pile.

en utilisant la récursion régulière, chaque appel récursif pousse une autre entrée sur la pile d'appels. Lorsque la récursion est terminée, l'application doit alors pop chaque entrée hors tout le chemin de retour vers le bas.

avec la récursion de la queue, le compilateur est capable de réduire la pile à une entrée, donc vous économisez de l'espace de pile...Une grande requête récursive peut effectivement provoquer un débordement de pile.

essentiellement des récursions de queue sont capables d'être optimisés en itération.

au lieu de l'expliquer avec des mots, voici un exemple. C'est une version Scheme de la fonction factorielle:

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

Voici une version de factoriel qui est retail-recursive:

(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 au fait est introduit dans l'expression de multiplication, et donc l'État doit être sauvegardé sur la pile lors de l'appel récursif. Dans la version recursive il y a aucun autre S-expression d'attente pour la valeur de l'appel récursif, et puisqu'il n'y est pas plus de travail à faire, l'état n'a pas à être sauvegardés sur la pile. En règle générale, les fonctions Scheme tail-recursive utilisent un espace de pile constant.

le fichier jargon a ceci à dire sur la définition de la récursion de la queue:

recursion de la queue / N./

si vous n'en avez pas déjà assez, voir recursion de la queue.

la récursion de la queue fait référence au dernier appel récursif dans la dernière instruction logique de l'algorithme récursif.

typiquement dans la récursion vous avez un de base qui est ce qui arrête les appels récursifs et commence à popping la pile d'appels. Pour utiliser un exemple classique, bien que plus C-ish que Lisp, la fonction factorielle illustre la récursion de la queue. L'appel récursif se produit après en vérifiant la condition de base.

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

Remarque, l'appel initial factorielle doit être factorielle(n, 1) où n est le nombre pour lequel la factorielle est d'être calculé.

cela signifie qu'au lieu d'avoir besoin de pousser le pointeur d'instruction sur la pile, vous pouvez simplement sauter au sommet d'une fonction récursive et continuer l'exécution. Cela permet aux fonctions de se reproduire indéfiniment sans déborder la pile.

j'ai écrit un blog post sur le sujet, qui a des exemples graphiques de ce que les cadres de pile ressemblent.

voici un extrait de code rapide comparant deux fonctions. La première est la récursion traditionnelle pour trouver le factoriel d'un nombre donné. La seconde utilise la recursion de la queue.

Très simple et intuitif à comprendre.

manière facile de dire si une fonction récursive est récursive de queue, est si elle renvoie une valeur concrète dans le cas de base. Ce qui signifie qu'il ne retourne pas 1 ou true ou quelque chose comme ça. Il est plus que probable qu'il retournera une variante de l'un de la méthode paramétrée.

une autre façon est de dire si l'appel récursif est libre de tout ajout, arithmétique, modification, etc... Ce qui signifie que son rien, mais 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);
}

contraste 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 tail call recursion est: un cas spécial de récursion où le dernier appel (ou l'appel de queue) est la fonction elle-même.

en Comparant les exemples fournis en Python:

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

^récursion

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

^RECURSION DE LA QUEUE

comme vous pouvez le voir dans la version récursive générale, le dernier appel dans le bloc de code est x + recsum(x - 1) . Si après avoir appelé la méthode recsum il y a une autre opération qui est x + .. .

toutefois, dans la version récursive de la 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 qu'aucune opération n'est effectuée par la suite.

ce point est important parce que la récursion de la queue comme vu ici ne fait pas grandir la mémoire parce que lorsque la VM sous-jacente voit une fonction s'appelant dans une queue position(la dernière expression à être évaluée dans une fonction), il élimine le cadre de pile actuel, qui est connu sous le nom D'optimisation de L'appel de queue (TCO).

EDIT

NB. Gardez à l'esprit que l'exemple ci-dessus est écrit en Python dont l'exécution ne supporte pas TCO. Ce n'est qu'un exemple pour expliquer ce point. TCO est supporté dans des langues comme Scheme, Haskell etc

voici un exemple de Lisp courant qui fait des factoriels en utilisant la recursion de la queue. En raison de la nature sans pile, on pourrait effectuer des calculs factoriels incroyablement grands ...

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

et puis pour le plaisir vous pourriez essayer (format nil "~R" (! 25))

en bref, une récursion de queue a l'appel récursif comme le dernier déclaration dans la fonction de sorte qu'il n'a pas à attendre l'appel récursif.

donc c'est une recursion de queue i.e. N(x - 1, p * x) est la dernière déclaration dans la fonction où le compilateur est intelligent pour comprendre qu'il peut être optimisé à un pour-boucle (factoriel). 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 façon non récursive d'écrire la fonction factorielle ci-dessus (bien que certains compilateurs C++ puissent 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 billet intitulé comprendre la récursion de la queue-Visual Studio C++ - Assembly View

voici une version 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
}

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

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

pour comprendre certaines des différences fondamentales entre la récursion de l'appel de queue et la récursion de l'appel de non-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 la récursion de l'appel de queue, tandis que F# l'optimise.

les différences de principe impliquent boucles vs Lambda calcul. C# est conçu avec des boucles à l'esprit tandis que F# est construit à partir des principes de Lambda calcul. Pour un très bon (et libre) livre sur les principes du calcul Lambda, voir: Structure et interprétation des programmes informatiques, 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 traite de la différence entre la recursion hors queue et la recursion par appel de queue (en F#): Recursion par rapport à la recursion hors queue en F sharp .

si vous voulez lire au sujet de certaines des différences de conception de la récursion de l'appel de queue entre C# et F#, voir: Generating Tail-Call Opcode in C# and F# .

si vous vous souciez assez de savoir quelles conditions empêchent le compilateur C# d'effectuer queue-appel d'optimisation, voir cet article: JIT CLR queue-appel conditions .

Ceci est un extrait de la Structure et l'Interprétation des Programmes d'Ordinateur sur la queue de la récursivité.

en contraste d'itération et de récursion, nous devons faire attention à ne pas confondre la notion d'un processus récursif avec la notion de procédure récursive. Lorsque nous décrivons une procédure récursive, nous sommes se référant au fait syntaxique que la définition de la procédure se réfère (directement ou indirectement) à la la procédure elle-même. Mais quand nous décrire un processus comme suit un modèle qui est, disons, linéairement récursive, nous parlons de la façon dont le processus évolue, pas sur la syntaxe de la façon dont une procédure est écrite. Il peut sembler troublant que nous nous référons à une procédure récursive comme iter comme la génération d'un processus itératif. Cependant, le processus est réellement itératif: son état est complètement capturé par ses trois variables d'état, et un besoin d'un interprète pour garder la trace de seulement trois variables afin exécuter le processus.

L'une des raisons pour lesquelles la distinction entre processus et procédure peut être la confusion est que la plupart des implémentations de langages communs (y compris Ada, Pascal, C) sont conçus de telle façon que l'interprétation de toute récursive procédure consomme une quantité de mémoire qui augmente avec le nombre de la procédure demande, même lorsque le processus décrit est, en principe, itératif. En conséquence, ces langues peuvent décrire itératif ne traite que par le recours à des constructions en boucle spéciales" comme do, répéter, jusqu'à ce que, pour, et tout. la mise en œuvre de Schéma ne partage pas ce défaut. Il exécutera un processus itératif dans l'espace constant, même si le processus itératif est décrit par une procédure récursive. Un l'implémentation avec cette propriété s'appelle tail-recursive. avec un tail-mise en œuvre récursive, l'itération peut être exprimée en utilisant le ordinaire procédure mécanisme d'appel, de sorte que l'itération spéciale les constructions 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 pile, encore et encore, parce qu'il n'y a aucune raison ou moyen de revenir à un cadre "précédent". Le passé est terminé et on peut le jeter. Vous obtenez un cadre, se déplaçant à jamais dans le futur, jusqu'à ce que votre processus meurt inévitablement.

_{L'analogie se décompose quand on considère que certains processus peuvent utiliser des cadres supplémentaires mais sont encore considérés queue-récursive si la pile ne croît pas à l'infini.}

il existe deux types de récursions de base: recursion de la tête et recursion de la queue.

Dans tête de récursivité , une fonction fait son appel récursif et puis effectue d'autres calculs, peut-être en utilisant le résultat du appel récursif, par exemple.

dans une fonction retail recursive , tous les calculs se font en premier et l'appel récursif est la dernière chose qui se passe.

from this super awesome post. Veuillez envisager de le lire.

récursion signifie une fonction qui s'appelle elle-même. Par exemple:

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

récursion de la queue, la récursion qui conclut 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 helper, la dernière chose qu'il fait si left n'est pas nul est de s'appeler (après contre quelque chose et cdr quelque chose). C'est essentiellement comme ça qu'on établit une liste.

la récursion de queue a un grand avantage que l'interperter (ou compilateur, dépendant du langage et du vendeur) peut l'optimiser, et le transformer en quelque chose d'équivalent à une boucle while. En fait, dans la tradition Scheme, la plupart des boucles "pour" et "tandis que" se font de la manière queue-récursion (il n'y a pas de pour et tandis, autant que je sache).

Cette question a beaucoup de bonnes réponses... mais je ne peux m'empêcher de penser à une autre façon de définir la "recursion de la queue", ou du moins "une recursion de la queue correcte"."À savoir: doit-on regarder comme une propriété d'une expression donnée dans un programme? Ou devrait-on le considérer comme une propriété d'un implémentation d'un langage de programmation ?

pour plus sur cette dernière vue, il ya un classique papier par Will Clinger, " Proper Tail Recursion and Space Efficiency "(PLDI 1998), qui définit" proper tail recursion " comme une propriété d'une implémentation de langage de programmation. La définition est construite pour permettre à quelqu'un d'ignorer les détails de la mise en œuvre (par exemple si la pile d'appels est réellement représentée via la pile d'exécution ou via une liste de cadres liés alloués en tas).

pour ce faire, il utilise l'analyse asymptotique: pas du temps d'exécution du programme comme on le voit habituellement, mais plutôt du programme utilisation de l'espace . De cette façon, l'utilisation de l'espace d'une liste liée allouée en tas par rapport à une pile d'appels runtime finit par être asymptotiquement équivalente; on peut donc ignorer ce détail d'implémentation du langage de programmation (un détail qui importe certainement un peu dans la pratique, mais qui peut brouiller les pistes un peu quand on tente de déterminer si une implémentation donnée satisfait à l'exigence d'être "propriété queue récursive")

Le document mérite une étude attentive pour un certain nombre de raisons:

• donne une définition inductive de la queue expressions et queue appelle d'un programme. (Une telle définition, et pourquoi de tels appels sont importants, semble être l'objet de la plupart des autres réponses ici.)

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

  définition 1 les tail expressions d'un programme écrit dans Core Scheme sont définies de façon 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 queue d'expression.

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

(un appel récursif de la queue, ou comme le dit le journal, "appel de la queue" est un cas particulier d'appel de 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 schéma de base, où chaque machine a le même comportement observable sauf pour la classe asymptotique complexité de l'espace que chacun est.

  par exemple, après avoir donné les définitions pour les machines avec respectivement, 1. basée sur la pile de gestion de la mémoire, 2. ramassage des ordures mais pas d'appels de queue, 3. la collecte des ordures et les appels de queue, le papier continue avec des stratégies de gestion de l'entreposage encore plus avancées, comme 4. "evlis queue recursion", où le l'environnement n'a pas besoin d'être préservé à travers l'évaluation du dernier argument de la sous-expression dans un appel de queue, 5. la réduction de l'environnement d'une fermeture à juste les variables libres de fermeture, et 6. la sémantique dite du " safe-for-space "telle que définie par Appel et Shao .

• afin de prouver que les machines appartiennent effectivement à six classes distinctes de complexité spatiale, le papier, pour chaque paire de machines en comparaison, fournit des exemples concrets de programmes qui exposeront l'explosion asymptotique de l'espace sur une machine mais pas l'autre.

(en lisant ma réponse maintenant, je ne suis pas sûr que j'ai réussi à saisir les points cruciaux du papier 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 appelle lui-même à la fin ("queue") de la fonction dans laquelle aucun calcul est fait après le retour de l'appel récursif. De nombreux compilateurs optimisent changer un appel récursif à une queue récursive ou itérative de l'appel.

envisager le problème de l'informatique factorielle d'un nombre.

une approche simple serait:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

supposons que vous appelez factoriel(4). L'arbre de récursion serait:

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

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

Cependant, considérons l'exemple suivant:

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

factTail(n):
   return factAux(1,n);

arbre de récursion pour factttail (4) serait:

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

ici aussi, la profondeur maximale de récursion est O(n) mais aucun des appels n'ajoute de variable supplémentaire à la pile. Par conséquent, le compilateur peut supprimer avec une pile.