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

Question

Tout en commençant à apprendre lisp, je suis tombé sur le terme queue-récursive.Que veut dire exactement?

Answer 1

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

Voici un simple JavaScript de mise en œuvre 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 permettrait d'é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 est à effectuer avant de l'interpréteur JavaScript commence à réellement faire le travail de calcul de la somme.

Voici une queue-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 séquence des événements qui pourraient 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, la running_total est mis à jour.

Note:L'original de la réplique utilisé des exemples de Python.Celles-ci ont été modifiés pour JavaScript, depuis modernes JavaScript interprètes de soutien la queue d'appel d'optimisation mais interpréteurs Python ne le font pas.

Answer 2

Dans traditionnelle 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 permet d'effectuer 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 (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 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 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.

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

Answer 5

L'utilisation de la récursivité, chaque appel récursif pousse une autre entrée sur la pile d'appel.Lorsque la récursivité est terminée, l'application doit éclater chaque entrée off tout le chemin du retour vers le bas.

Avec la queue de la récursivité, en fonction de la langue le compilateur peut être en mesure à l'effondrement de la pile vers le bas à une seule entrée, de sorte que vous économiser de l'espace de pile...Un grand requête récursive peut effectivement provoquer un débordement de pile.

Fondamentalement, la Queue récurrences peuvent être optimisées dans l'itération.

Answer 6

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 fonctions récursives terminales à l'utilisation constante de l'espace de pile.

Answer 7

Le jargon file a ceci à dire à propos de la définition de la queue de la récursivité:

la queue de la récursivité /n./

Si vous n'êtes pas malade déjà, voir la queue de la récursivité.

Answer 8

La queue de la 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 une 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 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é.

Answer 9

Cela signifie que, plutôt que d'avoir à pousser le pointeur d'instruction sur la pile, vous pouvez simplement sauter vers le haut d'une fonction récursive, et de continuer l'exécution.Cela permet pour les fonctions de répéter indéfiniment sans débordement de la pile.

J'ai écrit un blog post sur le sujet, qui a graphique des exemples de ce que la pile d'images ressemblent.

Answer 10

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

Answer 11

La meilleure façon pour moi de comprendre tail call recursion est un cas particulier de la récursivité où l' dernier appel(ou de la 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)

^La RÉCURSIVITÉ

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

^LA QUEUE DE LA RÉCURSIVITÉ

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

Cependant, dans la queue, une version récursive, le dernier appel(ou la queue d'appel) dans le bloc de code est tailrecsum(x - 1, running_total + x) ce qui signifie que le dernier appel à la méthode elle-même et aucune opération après que.

Ce point est important parce que la queue de la récursivité comme on le voit ici n'est pas de faire de la mémoire de grandir, car lorsque le sous-jacent VM voit un appel de fonction dans une queue de position (la dernière expression évaluée dans une fonction), il élimine l'actuel cadre de la pile, qui est connu comme la Queue d'Appel d'Optimisation(TCO).

MODIFIER

NB.Ne garder à l'esprit que l'exemple ci-dessus est écrit en Python, dont l'exécution ne prend pas en charge le coût de possession.C'est juste un exemple pour expliquer le point.TCO est pris en charge dans les langues comme le Régime, Haskell, etc

Answer 12

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

Answer 13

Voici 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 (format nil "~R" (! 25))

Answer 14

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

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

Answer 15

En bref, une queue de récursivité a l'appel récursif comme l' dernière déclaration de la fonction, afin de ne pas avoir à attendre l'appel récursif.

Donc, c'est une queue de récursivité c'est à direN(x - 1, p * x) est la dernière instruction de la fonction où le compilateur est intelligent pour comprendre qu'il peut être optimisé grâce à une boucle for (factorielle).Le deuxième paramètre p porte l'intermédiaire de la valeur du produit.

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

C'est le non-récursives terminales de l'écriture au-dessus de la fonction factorielle (bien que certains compilateurs C++ peuvent être en mesure d'optimiser 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é "La Compréhension De La Queue De La Récursivité – Visual Studio C++ – Vue D'Assemblage"

Answer 16

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

Answer 17

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

En contraste de l'itération et de la récursivité, nous devons être prudents de 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 à la syntaxiques fait que la définition de la procédure se réfère (directement ou indirectement) à la procédure elle-même.Mais quand nous décrire un processus, comme la suite d'un modèle qui est, disons, de façon linéaire 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 inquiétant que nous nous référons à une procédure récursive comme iter comme la génération d'un processus itératif.Toutefois, le processus est vraiment itératif:Son état est complètement capturé par ses trois variables d'état, et un interprète besoin de garder une trace de seulement trois variables pour exécuter le processus.

L'une des raisons que la distinction entre processus et de la procédure peut être déroutant, c'est que la plupart des implémentations de langages communs (y compris Ada, Pascal, et 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 les appels de procédure, même si le processus décrit est, en principe, itératif.En conséquence, ces langues peuvent décrire itératif les processus qu'en recourant à des fins spéciales “boucles” 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 va exécuter un processus itératif, la constante de l'espace, même si l' processus itératif est décrit par une procédure récursive.Un la mise en œuvre de cette propriété est appelée queue-récursive. Avec un queue-récursive de la mise en œuvre, l'itération peut être exprimée à l'aide de la procédure ordinaire mécanisme d'appel, de sorte qu'spécial itération les constructions ne sont utiles qu'en tant que sucre syntaxique.

Answer 18

La 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.}

Answer 19

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 de l'appel.

Considérons le problème de 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 la 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.

Answer 20

Comprendre certaines différences fondamentales qui existent entre la queue-appel de la récursivité et de la non-queue-appelons récursivité, nous pouvons explorer la .NET implémentations de ces techniques.

Voici un article avec quelques exemples en C#, F# et C++\CLI: Aventures dans la Queue de la Récursivité en C#, F# et C++\CLI.

C# n'est pas optimiser pour la queue-appel de la récursivité alors que F# ne.

Les différences de principe impliquer boucles vsLambda calcul.C# est conçu avec des boucles à l'esprit alors que F# est construit à partir des principes de Lambda calcul.Pour un très bon (et gratuit) livre sur les principes de Lambda calcul, voir La Structure et l'Interprétation des Programmes d'Ordinateur, par Abelson, Sussman, et Sussman.

Concernant les appels tail en F#, pour un très bon article d'introduction, voir Introduction détaillée à la Queue des Appels en F#.Enfin, voici un article qui couvre la différence entre les non-récursion sur la queue et la queue de l'appel de la récursivité (en F#): Tail-recursion vsnon la queue de la récursivité en fa dièse.

Si vous voulez lire sur certaines des différences de conception de la queue-appelons récursivité entre C# et F#, voir Générer la Queue-Appel Opcode en C# et F#.

Si vous vous souciez assez pour voulez savoir quelles sont les conditions d'empêcher le compilateur C# à partir de l'exécution de la queue-appel d'optimisation, voir cet article: JIT CLR queue-appel conditions.

Answer 21

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

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

Dans un queue récursive fonction, tous les calculs se produire d'abord et l'appel récursif est la dernière chose qui se passe.

Prises de cette super post.Veuillez considérer le lire.

Answer 22

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

Dans 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-de 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).

Answer 23

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 construit afin de permettre à 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 la queue des 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 L' queue expressions d'un programme écrit dans le Schéma de Base sont définis inductivement comme suit.

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

  Définition 2 Un appel tail 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 l' asymptotique 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 dans l'autre.

---

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

Answer 24

La fonction récursive est une fonction qui appels par lui-même

Il permet aux programmeurs d'écrire des programmes efficaces à l'aide d'un une quantité minimale de code.

L'inconvénient est qu'ils peuvent provoquer une boucle infinie et d'autres résultats inattendus si pas écrit correctement.

Je vais expliquer à la fois Simple fonction Récursive et la Queue fonction Récursive

Dans le but de rédiger un Simple fonction récursive

1. Le premier point à considérer est que lorsque vous devez décider sur le coming-out de la boucle qui est le cas de la boucle
2. Le deuxième est le processus à faire si nous sommes notre propre fonction

À partir de l'exemple donné:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

À partir de l'exemple ci-dessus

if(n <=1)
     return 1;

Est le facteur décisif au moment de sortir de la boucle

else 
     return n * fact(n-1);

Est le véritable traitement à faire

Permettez-moi de le découper les tâches une par une, pour faciliter la compréhension.

Nous allons voir ce qui se passe en interne, si je lance fact(4)

1. La substitution de n=4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If boucle échoue donc, il va à else boucle on en revient donc 4 * fact(3)

2. Dans la pile mémoire, nous avons 4 * fact(3)

   La substitution de n=3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If boucle échoue donc, il va à else boucle

on en revient donc 3 * fact(2)

Rappelez-vous que nous avons appelé ``4 * fact(3)`

La sortie pour fact(3) = 3 * fact(2)

Jusqu'à présent, la pile a 4 * fact(3) = 4 * 3 * fact(2)

3. Dans la pile mémoire, nous avons 4 * 3 * fact(2)

   La substitution de n=2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If boucle échoue donc, il va à else boucle

on en revient donc 2 * fact(1)

Rappelez-vous que nous avons appelé 4 * 3 * fact(2)

La sortie pour fact(2) = 2 * fact(1)

Jusqu'à présent, la pile a 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

3. Dans la pile mémoire, nous avons 4 * 3 * 2 * fact(1)

   La substitution de n=1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If la boucle est vrai

on en revient donc 1

Rappelez-vous que nous avons appelé 4 * 3 * 2 * fact(1)

La sortie pour fact(1) = 1

Jusqu'à présent, la pile a 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

Enfin, le résultat de fait(4) = 4 * 3 * 2 * 1 = 24

L' La Queue De La Récursivité serait

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

1. La substitution de n=4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If boucle échoue donc, il va à else boucle on en revient donc fact(3, 4)

2. Dans la pile mémoire, nous avons fact(3, 4)

   La substitution de n=3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If boucle échoue donc, il va à else boucle

on en revient donc fact(2, 12)

2. Dans la pile mémoire, nous avons fact(2, 12)

   La substitution de n=2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

If boucle échoue donc, il va à else boucle

on en revient donc fact(1, 24)

3. Dans la pile mémoire, nous avons fact(1, 24)

   La substitution de n=1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If la boucle est vrai

on en revient donc running_total

La sortie pour running_total = 24

Enfin, le résultat de fait(4,1) = 24

Answer 25

Beaucoup de gens ont déjà expliqué récursion.Je voudrais citer quelques réflexions à propos de quelques avantages que la récursivité donne de l'ouvrage “la Simultanéité dans .NET, les tendances Modernes de la simultanées et de la programmation parallèle” par Riccardo Terrell:

“La fonctionnelle de la récursivité est la voie naturelle pour itérer sur la PF, car il évite la mutation de l'état.Lors de chaque itération, une nouvelle valeur est passée dans la boucle constructeur au lieu d'être mis à jour (muté).Dans outre, une fonction récursive peut être composée, rendre votre programme plus modulaire, ainsi que d'introduire les possibilités de l'exploiter la parallélisation."

Voici également quelques notes intéressantes à partir du même livre sur la queue de la récursivité:

Queue-d'appel de la récursivité est une technique qui convertit régulièrement récursive fonction dans une version optimisée qui peut gérer de grandes entrées sans tous les risques et les effets secondaires.

REMARQUE La raison principale pour une queue appel, comme une optimisation est de améliorer la localité des données, l'utilisation de la mémoire, et l'utilisation du cache.En faisant une queue d'appel, l'appelant utilise le même espace de pile que l'appelant.Cela réduit la pression de la mémoire.Il améliore légèrement le cache parce que le même la mémoire est réutilisé pour la suite des appelants et peuvent rester dans le cache, plutôt que de les expulser, une ancienne ligne de cache pour faire de la place pour un nouveau cache ligne.

Answer 26

Un queue récursive la 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

Les compilateurs et interpréteurs de mettre en œuvre la queue d'appel d'optimisation ou la queue d'appel d'é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 une queue appeler 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 le 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.)

Les 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 un 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.

Answer 27

La queue de la Récursivité est assez rapide par rapport à la normale de la récursivité.Il est rapide, car la sortie des ancêtres appel ne sera pas écrit dans la pile de garder la piste.Mais la récursivité tous l'ancêtre des appels de sortie de l'écrit dans la pile de garder la piste.