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

Question

Tout en commençant à apprendre lisp, je suis tombé sur le terme de la queue-récursive. Ça veut dire quoi?

Answer 1

La queue de la récursivité est bien décrit dans les précédentes réponses, mais je pense qu'un exemple en action permettrait d'illustrer le concept.

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

Voici un Python de mise en œuvre qui utilise la récursivité:

def 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 Python serait à évaluer.

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 la façon dont chaque appel récursif doit remplir avant de l'interpréteur Python commence à réellement faire le travail de calcul de la somme.

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

def 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 allaient se produire si vous avez appelé, tailrecsum(5), (ce qui serait effectivement tailrecsum(5, 0), en raison de la valeur par défaut second argument).

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

Dans la queue-récursive cas, chaque évaluation de l'appel récursif, l' running_total est mis à jour.

Remarque: Comme indiqué dans les commentaires, Python n'a pas de prise en charge intégrée pour l'optimisation de loin la queue appels, donc il n'y a aucun avantage à le faire en Python. Toutefois, vous pouvez utiliser un décorateur pour réaliser l'optimisation.

Answer 2

Traditionnelle 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 la queue de la 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 sous la forme de "(de retour (récursif de la fonction params))" (je pense que c'est la syntaxe Lisp). 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 ceci est qu'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 la pile de 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.

Answer 3

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

while(E) { S }; return Q

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

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

Bien sûr, E, S, et Q doivent être définies pour calculer certains intéressant de valeur sur certaines variables. Par exemple, la boucle de la fonction

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

(Cet "habillage" de la queue-fonction récursive avec une fonction avec moins de paramètres est une commune fonctionnelle idiom.)

Answer 4

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 appel tail [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 une queue d'appel:

function f (x)
  return g(x)
end

Après f appelle 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 à la (ou appel) 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.

Answer 5

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

Voici une version de factorielle, c'est-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 de fonctions récursives terminales à l'utilisation constante de l'espace de pile.