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

Dans traditionnel de la récursivité, le modèle typique est que vous effectuez vos appels récursifs d'abord, et puis vous prenez la valeur de retour de l'appel récursif, et de calculer le résultat. De cette manière, vous n'obtenez pas le résultat de votre calcul jusqu'à ce que vous avez retourné à partir de chaque appel récursif.

Dans queue de récursivité, vous effectuez vos calculs en premier, et puis vous exécutez l'appel récursif, en passant les résultats de votre étape en cours de la prochaine étape récursive. Cette résultats dans la dernière instruction étant en forme de (return (recursive-function params)). Fondamentalement, la valeur de retour de tout récursive étape est la même que la valeur de retour de la prochaine appel récursif.

La conséquence de cela est que une fois que vous êtes prêt à effectuer votre prochaine étape récursive, vous n'avez pas besoin de la pile en cours de cadre plus. Cela permet de l'optimisation. En fait, avec un convenablement écrit compilateur, vous ne devriez jamais avoir un débordement de pile ricaner avec une queue appel récursif. Simplement réutiliser la pile en cours pour la prochaine étape récursive. Je suis sûr que Lisp ne ce.

Cet extrait du livre de la Programmation en Lua montre comment faire une queue de récursivité (en Lua, mais il devrait s'appliquer à Lisp trop) et pourquoi c'est mieux.

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

function f (x)
  return g(x)
end

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

Parce qu'une bonne queue appel n'utilise pas de
espace de pile, il n'y a pas de limite sur le
nombre de "niche" à la queue les appels 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 tail est un
type de goto. En tant que tel, un très utile
l'application d'une bonne queue dans les appels
Lua est pour la programmation des machines d'état.
Ces applications peuvent représenter chaque
de l'état par une fonction; pour changer l'état
est d'aller à (ou à l'appel d'une
fonction. Comme un exemple, laissez-nous
considérons un simple jeu de labyrinthe. Le labyrinthe
dispose de plusieurs chambres, chacune avec
quatre portes: nord, sud, est, et
à l'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 message d'avertissement. L'objectif est
pour aller d'une première salle de finale
chambre.

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

Ce n'est pas la queue récursive parce que vous avez encore des choses à faire (ajouter 1) dans cette fonction après l'appel récursif est faite. Si vous entrez un nombre très élevé, il ne sera probablement provoquer un débordement de pile.

Au lieu d'expliquer avec des mots, voici un exemple. C'est un Schéma de la version de la fonction factorielle:

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

Ici est une version de factorielle qui est de la queue-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 que dans la première version de l'appel récursif de fait est introduit dans la multiplication de l'expression, et donc l'état doit être sauvegardé sur la pile lors de la prise de l'appel récursif. Dans la queue, une version récursive il n'y a pas d'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, le Régime fonctions récursives terminales à l'utilisation constante de l'espace de pile.

Queue de récursivité se réfère à l'appel récursif est la dernière dans le dernier logique de l'instruction dans l'algorithme récursif.

Généralement dans la récursivité, vous avez un cas de base qui est-ce qui empêche les appels récursifs et commence à éclater la pile d'appel. Pour utiliser un exemple classique, bien que plus C-ish que Lisp, la fonction factorielle illustre la queue de la récursivité. L'appel récursif se produit après la vérification de la base de cas d'état.

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

L'appel initial factorielle serait factorial(n) où fac=1 (valeur par défaut) et n est le nombre pour lequel la factorielle est d'être calculé.

Voici un petit extrait de code de la comparaison de deux fonctions. La première est traditionnelle de la récursivité pour trouver la factorielle d'un nombre donné. La seconde utilise la récursivité tail.

Très simple et intuitif à comprendre.

Un moyen facile de savoir si une fonction récursive est une queue 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 true ou quelque chose comme ça. Il est plus que probable retour une variante de l'un des paramètres de la méthode.

Une autre façon est-à-dire si l'appel récursif est libre de tout ajout, l'arithmétique, de 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 un éventuel queue récursive de la mise en œuvre de la fonction de 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);
}

Cela contraste avec la norme récursive de mise en œuvre:

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

Ici est un Common Lisp exemple qui ne les factorielles à l'aide de la queue de la récursivité. En raison de la pile, moins de la nature, on pourrait effectuer incroyablement grande factorielle des calculs ...

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

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

ici est un Perl version 5 de la tailrecsum fonction mentionné plus tôt.

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
}

Une queue de récursivité est une fonction récursive, où les appels de fonction
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 de l'optimiser pour
changer un appel récursif à une queue récursive ou itérative appel.

Envisager le problème du calcul de la factorielle d'un nombre.

Une approche simple serait:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

Supposons que vous appelez factorielle(4). La récursivité de l'arbre serait:

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

Le maximum de profondeur 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);

La récursivité de l'arbre pour factTail(4) serait:

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

Ici aussi, le maximum de la profondeur de récursion est O(n), mais aucun des appels ajoute une variable supplémentaire à la pile. Donc le compilateur peut faire disparaître une pile.

Queue de la récursivité est la vie que vous vivez actuellement. Constamment à vous recycler la même trame de pile, encore et encore, car il n'y a pas de raison ou de moyens pour le retour à un "précédent" cadre". Le passé est fini et fait avec de sorte qu'il peut être mis au rebut. Vous obtenez une image, à jamais, à l'avenir, jusqu'à ce que votre processus inévitablement meurt.

_{L'analogie décompose lorsque vous envisagez de certains processus peuvent utiliser des images supplémentaires, mais sont toujours considérés comme des queue-récursive si la pile n'est pas croître à l'infini.}

Un queue récursive fonction est une fonction récursive où la dernière opération avant le retour, c'est de faire la fonction récursive appel. Qui est, la valeur de retour de la fonction récursive appel est immédiatement retourné. Par exemple, votre code devrait ressembler à ceci:

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

Compilateurs et interpréteurs de mettre en œuvre queue appeler l'optimisation ou queue appel élimination pouvez optimiser récursive code pour éviter les débordements de pile. Si votre compilateur ou l'interpréteur ne pas mettre en œuvre la queue d'appel d'optimisation (comme la Disponible interprète) il n'y a aucun avantage supplémentaire à l'écriture de votre code de cette façon.

Par exemple, c'est un standard de la fonction factorielle récursive en Python:

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

Et c'est un appel tail une version récursive de la fonction factorielle:

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

(Notez que même si c'est du code Python, le Disponible interprète ne fait pas la queue d'appel d'optimisation, de sorte que l'organisation de votre code comme celui-ci ne confère aucun d'exécution des prestations.)

Vous pourriez avoir à rendre votre code un peu plus illisible de faire usage de la queue d'appel d'optimisation, comme le montre la factorielle exemple. (Par exemple, le cas de base est maintenant un peu peu intuitive, et la accumulator paramètre est utilisé efficacement comme une sorte de variable globale.)

Mais l'avantage de la queue d'appel d'optimisation est qu'il empêche les erreurs de dépassement de pile. (Je note que vous pouvez obtenir ce même résultat en utilisant un algorithme itératif au lieu d'un récursive.)

Débordements de pile sont causées lorsque la pile d'appel a eu trop d'objets d'image poussé sur. Une image de l'objet est poussé sur la pile d'appel lorsqu'une fonction est appelée, et a sauté hors de la pile d'appel lorsque la fonction retourne. Objets d'image contenant des informations telles que les variables locales et quelle ligne de code pour revenir à quand la fonction retourne.

Si votre fonction récursive fait trop d'appels récursifs sans retour, la pile d'appel peut dépasser son objet frame limite. (Le nombre varie selon la plate-forme; en Python il est de 1000 objets d'image par défaut.) Cela provoque une débordement de pile erreur. (Hey, c'est là que le nom de ce site web vient d'!)

Toutefois, si la dernière chose que votre fonction récursive n'est de faire de l'appel récursif et renvoie sa valeur de retour, alors il n'y a aucune raison qu'il a besoin de garder l'image actuelle de l'objet doit rester sur la pile d'appel. Après tout, si il n'y a pas de code après l'appel de fonction récursive, il n'y a pas de raison de s'accrocher à l'image actuelle de l'objet de variables locales. Donc, nous pouvons nous débarrasser de l'image actuelle de l'objet immédiatement plutôt que de le garder sur la pile d'appel. Le résultat final est que votre pile d'appel de ne pas grandir en taille, et ne peut donc pas de débordement de pile.

Un compilateur ou l'interpréteur doit avoir la queue d'appel d'optimisation d'une fonction pour qu'il soit capable de reconnaître quand la queue d'appel d'optimisation peut être appliquée. Même alors, vous pouvez avoir réorganiser le code de votre fonction récursive de faire usage de la queue d'appel d'optimisation, et c'est à vous, si cette diminution potentielle de la lisibilité est la valeur de l'optimisation.

La récursivité moyen d'un appel de fonction elle-même. Par exemple:

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

Tail-Recursion signifie la récursivité que conclure de la fonction:

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

Voir, la dernière chose que l'onu-clos de la fonction (procédure, dans le Schéma de jargon), c'est d'appeler lui-même. L'autre (plus utile) exemple:

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

À l'aide de la procédure, la DERNIÈRE chose qu'il fait, si la gauche n'est pas nul, est d'appeler lui-même (APRÈS les contre quelque chose et cdr quelque chose). C'est fondamentalement la façon dont vous carte une liste.

La queue-la récursivité est un grand avantage que l'interprète (ou le compilateur, dépend de la langue et le vendeur) peut l'optimiser et de le transformer en quelque chose d'équivalent à une boucle while. Comme question de fait, dans le Schéma de la tradition, la plupart des "pour" et "boucle" while est fait en une queue-de récursivité manière (il n'y est pas et tout, autant que je sache).

Cette question a beaucoup de bonnes réponses... mais je ne peux pas aider mais carillon avec une autre de prendre sur la façon de définir la "queue de la récursivité", ou au moins "bonne queue de récursivité." À savoir: doit-on regarder comme une propriété d'une expression donnée dans un programme? Ou doit-on regarder comme une propriété d'un la mise en œuvre d'un langage de programmation?

Pour en savoir plus sur le dernier point de vue, il est un classique papier par la Volonté Clinger, "la Bonne Queue de Récursivité et de l'Efficacité de l'Espace" (PLDI 1998), qui a défini "la bonne queue de récursivité" en tant que propriété d'un langage de programmation de mise en œuvre. La définition est construite de façon à permettre d'ignorer les détails de mise en œuvre (comme par exemple si la pile d'appel est en fait représenté par l'exécution de la pile ou par l'intermédiaire d'un segment de mémoire allouée lié liste d'images).

Pour ce faire, il utilise l'analyse asymptotique: pas de temps d'exécution du programme que l'on voit habituellement, mais plutôt de programme l'utilisation de l'espace. De cette façon, l'utilisation de l'espace d'un segment de mémoire allouée liste liée vs un moteur d'exécution de la pile des appels finit par être asymptotiquement équivalent; donc, on en vient à ignorer que le langage de programmation de mise en œuvre détail (un détail qui a certainement des questions tout à fait un peu de pratique, mais il peut brouiller les pistes tout à fait un peu lorsque l'on tente de déterminer si une œuvre est de satisfaire à l'exigence d'être "la propriété de la queue récursive")

Le papier est intéressant de l'étude minutieuse d'un certain nombre de raisons:

• Il donne une définition inductive de la queue expressions et queue appels 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 La queue expressions d'un programme écrit dans le Schéma de Base sont définis inductivement comme suit.

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

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

(une queue appel récursif, ou comme le dit le rapport, "l'auto-appel tail" est un cas particulier d'une queue d'appel où la procédure est appelée elle-même.)

• Il fournit des définitions pour six différents "machines" pour l'évaluation du Schéma de Base, où chaque machine a le même comportement observable sauf pour la asymptotique de l'espace classe de complexité que chacun est en.

  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. la collecte des ordures, mais pas de queue appels, 3. la collecte des ordures et de la queue des appels, le papier continue de l'avant avec encore plus de stockage de pointe stratégies de gestion, tels que le 4. "evlis queue de récursivité", où l'environnement n'a pas besoin d'être conservées dans l'évaluation de la dernière sous-argument d'expression dans une queue d'appel, 5. la réduction de l'environnement d'une fermeture à juste les variables libres de fermeture, et 6. soi-disant "sécurité-pour-l'espace" sémantique tel que défini par D'Appel et de Shao.

• Afin de prouver que les machines appartiennent en fait à six distincts de l'espace de la complexité des classes, le papier, pour chaque paire de machines à sous de comparaison, fournit des exemples concrets de programmes qui permettront d'exposer asymptotique de l'espace blowup sur une seule machine, mais pas les autres.

(Lire par-dessus ma réponse maintenant, je ne sais pas si je suis parvenu à réellement capturer les points cruciaux de la Clinger papier. Mais, hélas, je ne peux pas consacrer plus de temps à l'élaboration de cette réponse à l'heure actuelle.)