Question Quelle est la récurrence de la queue?


En commençant à apprendre le zézaiement, je suis tombé sur le terme queue-récursive. Qu'est-ce que cela signifie exactement?


1294
2017-08-31 18:21


origine


Réponses:


Considérons une fonction simple qui ajoute les N premiers entiers. (par exemple. 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 avez appelé recsum(5), c'est 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 réellement à effectuer le travail de calcul de la somme.

Voici une version récursive de la queue 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 séquence des événements qui se produiraient si vous appelez tailrecsum(5), (qui serait effectivement tailrecsum(5, 0), à cause du deuxième 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 de la queue récursive, à chaque évaluation de l'appel récursif, le running_total Est mis à jour.

Note: La réponse originale utilisait des exemples de Python. Ceux-ci ont été changés en JavaScript, puisque les interprètes JavaScript modernes supportent optimisation de l'appel de queue mais les interprètes Python ne le font pas.


1292
2017-08-29 03:57



Dans 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 pas le résultat de votre calcul tant que vous n'êtes pas revenu de chaque appel récursif.

Dans récursion de la 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. 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 pile actuel. Cela permet une certaine optimisation. En fait, avec un compilateur correctement écrit, vous ne devriez jamais avoir un débordement de pile snicker avec un appel récursif de la queue. Il suffit de réutiliser le cadre de la pile en cours pour la prochaine étape récursive. Je suis sûr que Lisp fait ça.


546
2017-08-31 17:29



Un point important est que la récursivité de la queue est essentiellement équivalente à la boucle. 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

while(E) { S }; return Q

E et Q sont des expressions et S est une séquence d'instructions, et le transformer en une fonction récursive de la 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 bouclage

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

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

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 en queue avec une fonction avec moins de paramètres est un idiome fonctionnel commun.)


165
2017-08-29 16:03



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

UNE appel de queue [queue récursion] est une sorte de goto habillé   comme un appel. Un appel de queue se produit quand un   fonction appelle un autre comme son dernier   l'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 appels g, il n'a rien d'autre   faire. Dans de telles situations, le programme   n'a pas besoin de retourner à l'appel   fonction lorsque la fonction appelée   prend fin. Par conséquent, après l'appel de queue,   le programme n'a pas besoin de garder   des informations sur la fonction d'appel   dans la pile. ...

Parce qu'un appel de queue approprié n'utilise pas   empiler l'espace, il n'y a pas de limite sur le   nombre de "queue" imbriqués appelle un   programme peut faire. Par exemple, nous pouvons   appelez la fonction suivante avec n'importe quel   nombre comme argument; ça ne sera jamais   déborder 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   genre de goto. En tant que tel, un très utile   l'application de bons appels de queue dans   Lua est pour la programmation de machines d'état.   De telles applications peuvent représenter   état par une fonction; changer d'état   est d'aller à (ou d'appeler) un spécifique   fonction. À titre d'exemple, laissez-nous   Considérez un jeu de labyrinthe simple. Le labyrinthe   a plusieurs chambres, chacune avec jusqu'à   quatre portes: nord, sud, est et   Ouest. À chaque étape, l'utilisateur entre un   direction du mouvement. S'il y a une porte   dans cette direction, l'utilisateur va à   la pièce correspondante; sinon, le   programme imprime un avertissement. Le but est   passer d'une salle initiale à une finale   chambre.

Ce jeu est une machine d'état typique,   où la pièce actuelle est l'état.   Nous pouvons mettre en œuvre un tel labyrinthe avec un   fonction pour chaque pièce. Nous utilisons la queue   appelle à passer d'une pièce à   un 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 récursif de queue car 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 provoquera probablement un débordement de pile.


110
2017-08-29 03:55



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écursion est terminée, l'application doit ensuite déconnecter chaque entrée tout le chemin vers le bas.

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

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


57
2017-08-29 03:57



Au lieu de l'expliquer avec 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 à la queue:

(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 aux faits est introduit dans l'expression de multiplication, et que l'état doit donc être sauvegardé sur la pile lors de l'appel récursif. Dans la version récursive en queue, aucune autre expression S n'attend la valeur de l'appel récursif et comme il n'y a pas d'autre travail à faire, l'état n'a pas besoin d'être sauvegardé sur la pile. En règle générale, les fonctions de récurrence de queue Scheme utilisent un espace de pile constant.


56
2017-08-29 07:21



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

récursion de la queue /n./

Si vous n'en avez pas déjà assez, voyez la récursion de la queue.


52
2017-08-29 03:57



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

Typiquement en récursivité vous avez un cas de base qui est ce qui arrête les appels récursifs et commence à faire sauter la pile des appels. Pour utiliser un exemple classique, bien que plus C-ish que Lisp, la fonction factorielle illustre la récurrence de la queue. L'appel récursif se produit après vérifier la condition de base.

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

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


23
2017-08-31 23:52



Cela signifie qu'au lieu d'avoir à pousser le pointeur d'instruction sur la pile, vous pouvez simplement passer en haut d'une fonction récursive et continuer l'exécution. Cela permet aux fonctions de se répéter indéfiniment sans déborder la pile.

J'ai écrit un Blog poster sur le sujet, qui a des exemples graphiques de ce que les cadres de la pile ressemblent.


20
2017-10-14 21:20



Voici un extrait de code rapide comparant deux fonctions. Le premier est la récursion traditionnelle pour trouver la factorielle d'un nombre donné. La seconde utilise la récursivité de la queue.

Très simple et intuitif à comprendre.

Un moyen facile de dire si une fonction récursive est récursive en queue, c'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 retournera plus probablement une variante de l'un des paramètres de la méthode.

Une autre façon est de dire si l'appel récursif est libre de toute addition, arithmétique, modification, etc ... Signifiant que c'est rien, mais un appel récursif pur.

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);
    }
}

13
2017-10-01 22:06