Récursion de queue

Dans le de l'informatique, la récursion de queue de (ou la récursion de queue-extrémité de ) est un cas spécial de la récursion dans lequel la dernière opération de la fonction est un appel récursif. De telles récursions peuvent être facilement transformées aux itérations. Le remplacement de la récursion par l'itération , manuellement ou automatiquement, peut rigoureusement diminuer la quantité de l'espace de la pile utilisé et améliorer l'efficacité. Cette technique est utilisée généralement avec des langues de la programmation fonctionnelle , où l'approche déclarative et manipulation explicite de de l'état favorisent l'utilisation des fonctions récurrentes qui rempliraient autrement rapidement pile des appels .

Description

Quand une fonction s'appelle, l'ordinateur doit " ; remember" ; l'endroit il s'est appelé de, l'adresse de retour de , de sorte qu'il puisse retourner à cet endroit avec le résultat une fois que l'appel soit complet. Typiquement, cette information est sauvée sur la pile, une liste simple d'endroits de retour par ordre de temps que les endroits d'appel qu'ils décrivent ont été atteints. Parfois, la dernière chose qu'une fonction fait après exécution de toutes autres opérations est d'appeler simplement une fonction, probablement elle-même, et renvoie son résultat. Mais dans ce cas-ci, il n'y a aucun besoin de se rappeler l'endroit que nous appelons du &mdash ; au lieu de cela, nous pouvons laisser la pile seule, et la fonction nouvellement appelée renverra son résultat directement au visiteur original du . Convertissant un appel en branche ou saut en ce cas s'appelle une optimisation d'appel de queue de . Noter que l'appel de queue ne doit pas apparaître lexicologique après tous autres rapports dans le code source ; il est seulement important que son résultat soit immédiatement retourné, puisque la fonction d'appel n'obtiendra jamais une chance de faire n'importe quoi après l'appel si l'optimisation est exécutée.

Pour des appels de fonction normaux et non récurrents, ceci est habituellement une micro-optimisation qui ménage peu d'heure et espace, puisqu'il n'y a pas que beaucoup de différentes fonctions disponibles pour appeler. En traitant des fonctions récursives ou mutuellement récurrentes, cependant, l'espace de pile et le nombre de retours ont économisé peut devenir des nombres importants, puisqu'une fonction peut s'appeler, directement ou indirectement, un nombre important de périodes. En fait, il ramène souvent asymptotiquement espace requis de pile de linéaire, ou du O (n), à la constante, ou au O (1).

Si plusieurs fonctions sont le mutuellement récursif, signifiant elles chaque appel un un autre, et chaque appel elles font à un un autre dans des utilisations d'un ordre d'exécution un appel de queue, alors l'optimisation d'appel de queue donnera un coupent la queue correctement l'exécution récursive de qui ne consomme pas l'espace de pile. L'optimisation appropriée de récursion de queue est exigée par les définitions standard de quelques langages de programmation, tels que l'arrangement .

La notion de la position de queue dans l'arrangement peut être définie comme suit : le

le corps d'une expression de lambda est en position de queue.

de Le si le de (si E₂ de E₁ de E₀ ) est en position de queue, puis E₁ et E₂ sont en position de queue.

Exemples

Prendre ce programme de l'arrangement comme exemple :

lang=" de (définir (n) factoriel (définir (CRNA de fac-temps n) (si (= n 0) CRNA (fac-temps (- n 1) (* CRNA n)))) (si (< n 0) (" d'affichage ; Faire du tort l'argument ! " ;) (fac-temps n 1)))

Comme vous pouvez voir, le procédé intérieur fac-times s'appelle dernier dans le flux de commande. Ceci permet à un interprète ou au compilateur de réorganiser l'exécution qui ressemblerait d'habitude à ceci :

appel (3) factoriel fac-temps d'appel (3 1) fac-temps d'appel (2 3) fac-temps d'appel (1 6) fac-temps d'appel (0 6) retour 6 retour 6 retour 6 retour 6 retour 6

dans plus de variante efficace du de l'espace (et time-) :

appel (3) factoriel remplacer les arguments par (3 1), sautent au " ; fac-times" ; remplacer les arguments par (2 3), sautent au " ; fac-times" ; remplacer les arguments par (1 6), sautent au " ; fac-times" ; remplacer les arguments par (0 6), sautent au " ; fac-times" ; retour 6

Cette réorganisation ménage de l'espace parce qu'aucun état excepté l'adresse de la fonction d'appel ne doit être sauvé, sur la pile ou sur le tas. Ceci signifie également que le programmeur n'a pas besoin de s'inquiéter de manquer de l'espace de pile ou de tas pour des récursions extrêmement profondes.

Quelques programmeurs travaillant dans des langues fonctionnelles récriront le code récursif pour être queue-récursifs ainsi ils peuvent tirer profit de ce dispositif. Ceci exige souvent l'addition d'un " ; accumulator" ; argument (acc dans l'exemple ci-dessus) à la fonction. Dans certains cas (comme les listes de filtrage) et dans quelques langues, la pleine récursion de queue peut exiger une fonction qui était précédemment purement fonctionnelle pour être écrite tels qu'elle subit une mutation des références stockées dans l'autre variables.< ! -- un exemple serait bon ici -->

Sans compter que l'efficacité de l'espace et d'exécution, l'optimisation de récursion de queue est importante dans l'idiome de la programmation fonctionnelle connu sous le nom de suite de passant le modèle (cps), qui manquerait autrement rapidement de l'espace de pile.

Escroqueries de modulo de récursion de queue

Les escroqueries de du modulo de récursion de queue de est une généralisation de récursion de queue présentée par le David H. Car le nom suggère, la seule opération a eu besoin après que l'appel récursif soit les escroqueries d'un , qui ajoute un nouvel élément à l'avant de la liste qui a été renvoyée. L'optimisation déplace cette opération à l'intérieur de l'appel récursif en créant un noeud de liste avec l'élément avant, et en passant une référence à ce noeud comme argument.

Par exemple, considérer une fonction qui reproduit une liste chaînée, décrite ici dans le C : lang=" de *duplicate de liste (*input de liste de const) { si (NULLE de == d'entrée) { NULLE de retour ; } autrement { *head de liste = malloc (*head de sizeof) ; head->value = input->value ; head->next = reproduction (input->next) ; tête de retour ; } }

Sous cette forme la fonction n'est pas queue-récursive, parce que la commande revient au visiteur après l'appel récursif pour placer la valeur de head->next. Mais sur la reprise, le visiteur ajoute simplement une valeur au résultat de l'appelé. Ainsi la fonction est queue-récursive, sauf pour un " ; cons" ; l'action, c., coupent la queue des escroqueries récursives de modulo. La méthode de Warren donne l'exécution purement queue-récursive suivante :

lang=" de *duplicate de liste (*input de liste de const) { *head de liste ; duplicate_prime (entrée, &head) ; tête de retour ; } duplicate_prime vide (*input de liste de const, liste ** p) { si (NULLE de == d'entrée) { *p = NULLE ; } autrement { *p = malloc (sizeof ** p) ; (*p) - >value = input->value ; duplicate_prime (input->next, et (*p) - >next) ; } }

Note comment l'appelé appose maintenant à la fin de la liste, plutôt que font ajouter au début au visiteur au commencement.

L'exécution correctement queue-récursive peut être convertie en forme itérative : lang=" de *duplicate de liste (*input de liste de const) { *head de liste ; liste ** p = &head ; tandis que (entrée ! = NULLE) { *p = malloc (sizeof ** p) ; (*p) - >value = input->value ; entrée = input->next ; p = et (*p) - >next ; } *p = NULLE ; tête de retour ; }

Méthodes d'exécution

La récursion de queue est importante pour quelques langages de haut niveau évolués , particulièrement langues fonctionnelles de et les membres du blèsent famille de . Dans ces langues, la récursion de queue est la manière la plus utilisée généralement (et parfois la seule manière disponible) de mettre en application l'itération. Les spécifications de langue de l'arrangement exigent que des opérations queue-récursives doivent être optimisées pour pour ne pas élever la pile. Des appels de queue peuvent également être employés dans Perl , avec une variante du " ; goto" ; rapport qui prend un nom de fonction : &NAME de goto ;

Puisque beaucoup de compilateurs de l'arrangement emploient le C comme code intermédiaire de cible, le problème descend à la récursion de queue de codage dans C sans élever la pile. Beaucoup de réalisations réalisent ceci en utilisant un dispositif connu sous le nom de trempoline , un morceau de de code qui appelle à plusieurs reprises des fonctions. Toutes les fonctions sont écrites par l'intermédiaire du trempoline. Quand une fonction doit appeler des autres, au lieu de la lui appeler directement renvoie l'adresse de la fonction à s'appeler, les arguments à employer, et ainsi de suite, au trempoline. Ceci s'assure que la pile de C ne se développe pas et itération peut continuer indéfiniment.

Using un trempoline pour tous les appels de fonction est un peu plus cher que l'appel de fonction normal de C, tellement au moins un compilateur d'arrangement, le poulet , utilisations de qu'une technique a décrites la première fois par Baker de Henry de d'une suggestion non publiée par le Andrew Appel , dans lequel C normal ; des appels sont employés mais la taille de pile est vérifiée avant chaque appel. Quand la pile atteint sa taille autorisée maximum, des objets sur la pile ordure-sont rassemblés using l'algorithme de Cheney de en entrant toute des données de phase dans un tas séparé. Après ceci, la pile est déroulée (" ; popped" ;) et le programme reprend de l'état sauvé juste avant la collection d'ordures. Baker dit le " ; La méthode d'Appel évite de faire un grand nombre de petits rebonds de trempoline en sautant de temps en temps outre de l'état Building.

Random links: