Quel est l'avantage d'utiliser la récursivité de la queue ici?

Question 1

Un appel de fonction récursif de queue permet au compilateur d'effectuer une optimisation spéciale qu'elle ne peut normalement pas avec une récursivité régulière. Dans une fonction récursive de queue, l'appel récursif est la toute dernière chose à exécuter. Dans ce cas, au lieu d'allouer une trame de pile pour chaque appel, le compilateur peut retravailler le code pour simplement réutiliser le cadre de pile actuel, ce qui signifie qu'une fonction réécursive de queue n'utilisera qu'un cadre de pile unique par opposition à des centaines ou même à des milliers.

Cette optimisation est possible car le compilateur sait qu'une fois l'appel récursif de queue, aucune copie précédente des variables ne sera nécessaire, car il n'y a plus de code à exécuter. Si, par exemple, une instruction d'impression suivait un appel récursif, le compilateur devrait connaître la valeur de la variable à imprimer après les retours de l'appel récursif, et donc le cadre de pile ne peut pas être réutilisé.

Voici la page Wiki si vous souhaitez plus d'informations sur la façon dont cette "enregistrement d'espace" et la réutilisation de pile fonctionne réellement, ainsi que des exemples: Appel à queue

Edit: Je n'ai pas expliqué comment cela s'applique à Quicksort, n'est-ce pas? Eh bien, certains termes sont lancés dans cet article qui rendent tout déroutant (et certains d'entre eux sont tout simplement faux). La première fonction donnée (Quicksort) fait un appel récursif à gauche, un appel récursif à droite, puis sort. Notez que l'appel récursif à droite est la toute dernière chose qui se produit dans la fonction. Si le compilateur prend en charge l'optimisation récursive de la queue (expliquée ci-dessus), seuls les appels de gauche créent de nouvelles cadres de pile; Tous les bons appels réutilisent simplement le cadre actuel. Cela peut économiser quelques Empiler les cadres, mais peut toujours souffrir du cas où la partition crée une séquence d'appels où l'optimisation de la récursivité de la queue n'a pas d'importance. De plus, même si les appels côté droit utilisent le même cadre, les appels côté gauche appelés dans Les appels à droite utilisent toujours la pile. Dans le pire des cas, la profondeur de la pile est N.

La deuxième version décrite est ne pas Une queue qui récursive Quicksort, mais plutôt un Quicksort, seul le tri de gauche se fait récursivement, et le tri droit est effectué en utilisant la boucle. En fait, ce Quicksort (comme décrit précédemment par un autre utilisateur) ne peut pas avoir l'optimisation de la récursivité de la queue qui lui est appliquée, car l'appel récursif n'est pas la dernière chose à exécuter. Comment cela marche-t-il? Lorsqu'il est implémenté correctement, le premier appel à Quicksort est le même qu'un appel côté gauche dans l'algorithme d'origine. Cependant, aucun appel récursif côté droit n'est même appelé. Comment cela marche-t-il? Eh bien, la boucle s'occupe de cela: au lieu de trier "à gauche alors à droite", il trie la gauche avec un appel, puis trie la droite en triant continuellement uniquement le les gauches de droite. C'est vraiment un son ridicule, mais il s'agit essentiellement de trier tellement de gauches que les droits deviennent des éléments uniques et n'ont pas besoin d'être triés. Cela supprime efficacement la bonne récursivité, ce qui rend la fonction moins récursive (pseudo récursif, si vous voulez). Cependant, l'implémentation réelle ne choisit pas uniquement le côté gauche à chaque fois; Il choisit le plus petit côté. L'idée est toujours la même; Il ne fait essentiellement qu'un appel récursif d'un côté au lieu des deux. La sélection du côté plus court garantira que la profondeur de la pile ne peut jamais être plus grande que Log2 (n), qui est la profondeur d'un arbre binaire approprié. En effet, le côté le plus court sera toujours au maximum de la moitié de la taille de notre section de tableau actuelle. La mise en œuvre donnée par l'article ne garantit cependant pas cela, car elle peut souffrir du même scénario du pire des cas de "gauche est l'arbre entier". Cet article donne en fait une assez bonne explication à ce sujet si vous êtes prêt à faire plus de lecture: Sélection efficace et tri partiel basé sur Quicksort

Question 2

L'avantage, l'intégralité de la version "Recursive / Itérative" mixte, c'est-à-dire la version qui traite une sous-gamme par récursivité et une autre sous-gamme par itération, est qu'en choisissant laquelle des deux sous-chaînes à traiter récursive, vous pouvez garantir que la profondeur de la récursivité ne dépassera jamais log2 N, peu importe à quel point le choix du pivot est mauvais.

Pour le TAIL-RECURSIVE-QUICKSORT pseudocode fourni dans la question, où le traitement récursif est effectué d'abord par un appel récursif littéral, cet appel récursif doit être donné plus court sous-gamme. Que lui-même s'assurera que la profondeur de la récursivité sera limitée par log2 N. Ainsi, afin d'atteindre la garantie de profondeur de récursivité, le code doit absolument comparer les longueurs des sous-plages avant de décider quel sous-gamme à traiter par appel récursif.

Une mise en œuvre appropriée de cette approche pourrait ressembler à la suivante (emprunter votre pseudocode comme point de départ)

HALF-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      if (q - p < r - q)
        HALF-RECURSIVE-QUICKSORT(A, p, q-1)
        p = q+1
      else
        HALF-RECURSIVE-QUICKSORT(A, q+1, r)
        r = q-1

La TAIL-RECURSIVE-QUICKSORT Le pseudocode que vous avez fourni ne tente aucune tentative de comparer les longueurs des sous-plages. Dans ce cas, il n'offre aucun avantage. Et non, ce n'est pas vraiment "la queue récursive". Quicksort ne peut pas être réduit à un algorithme de rédaction de la queue.

Si vous effectuez une recherche Google sur les termes "QSort LogUy HigUy", vous trouverez facilement de nombreux cas d'une autre implémentation Quicksort populaire (style de bibliothèque standard) basé sur la même idée d'utilisation de la récursivité pour une seule des deux sous-plages . Cette implémentation pour les plates-formes 32 bits utilise une pile explicite de profondeur maximale de ~ 32 spécifiquement car elle peut garantir que la profondeur de récursivité ne sera jamais plus élevée que cela. (De même, les plates-formes 64 bits n'auront besoin que d'une profondeur de pile de ~ 64.)

La QUICKSORT La version qui fait deux appels récursifs littéraux est nettement pire à cet égard, car le mauvais choix répétitif de pivot peut atteindre une profondeur de récursivité très élevée, jusqu'à N au pire des cas. Avec deux appels récursifs, vous ne pouvez pas garantir que la profondeur de la récursivité sera limitée par log2 N. Un compilateur intelligent pourrait être en mesure de remplacer l'appel de fuite à QUICKSORT avec itération, c'est-à-dire tourner votre QUICKSORT Dans votre TAIL-RECURSIVE-QUICKSORT, mais il ne sera pas assez intelligent pour effectuer la comparaison de la longueur des sous-plans.

Question 3

Avantage de l'utilisation de la excursion de la queue: = de sorte que le compilateur optimise le code et le convertissez en un code non rérécise.

Avantage du code non économique par rapport à un récursif: = Le code non réécursif nécessite moins de mémoire pour s'exécuter que celle récursive. Cela est dû aux cadres de pile inactifs que la récursivité consomme.

Voici la partie intéressante: - même si les compilateurs boîte La théorie effectue cette optimisation, ils ne le font pas. Même les compilateurs répandus comme Dot-Net et Java n'effectuent pas cette optimisation.

Un problème auquel toutes les optimisations de code sont confrontées est le sacrifice de la capacité de débogage. Le code optimisé ne correspond plus au code source, de sorte que les traces de pile et les détails de l'exception ne peuvent pas être facilement comprises. Le code haute performance ou les applications scientifiques sont une chose, mais pour la majorité des applications de consommation, le débogage est requis même après la libération. Par conséquent, les optimisations ne sont pas effectuées vigoureusement.

s'il te plait regarde:

Question 4

Il semble y avoir une confusion de vocabulaire ici.

La première version est-ce que la queue est-ce que la dernière déclaration est un appel récursif:

QUICKSORT(A, p, r)
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

Si vous appliquez l'optimisation de la récupération de la queue, qui consiste à convertir la récursivité en boucle, vous obtenez la seconde, qui n'est plus de réécursive de la queue:

TAIL-RECURSIVE-QUICKSORT(A, p, r)
  while p < r
    q = PARTITION(A, p, r)
    TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
    p = q+1

L'avantage de cela est que généralement, vous aurez besoin de moins de mémoire de pile. Pourquoi donc? Pour comprendre, imaginez que vous voulez trier un tableau avec 31 éléments. Dans le cas hautement improbable que toutes les partitions sont parfaites, c'est-à-dire qu'ils divisent le tableau en plein milieu, votre profondeur de récursivité serait 4. En effet, la première scission donnerait deux partitions de 15 éléments, les deux secondes de deux partitions de 7 éléments, Le troisième un des 3 éléments, et après le quatrième, tout est trié.

Mais les partitions sont rarement aussi parfaites. En conséquence, toutes les récursitions ne sont pas tout aussi profondes. Dans notre exemple, vous pourriez en avoir certains qui ne sont que trois niveaux de profondeur, et certains qui sont 7 ou plus (le pire des cas est 30). En éliminant la moitié des récursions, vous avez de bonnes chances que votre profondeur de récursivité maximale soit moindre.

Comme l'a souligné Andreyt, les gammes sont souvent comparées pour s'assurer que la plus grande partition est toujours traitée de manière itérative, et la plus petite récursive. Cela garantit la plus petite profondeur de récursivité possible pour une stratégie de sélection de contribution et de pivot donnée.

Mais ce n'est pas toujours le cas. Parfois, les gens veulent produire des résultats dès que possible, ou ne souhaitent trouver et trier que les n premier éléments. Dans ces cas, ils veulent toujours trier la première partition avant la seconde. Même dans cette situation, l'élimination de la récursivité de la queue améliore généralement l'utilisation de la mémoire et ne l'aggrave jamais.

Question 5

Je ne sais pas exactement si c'est le bon endroit pour demander ce doute ou j'aurais dû poster une nouvelle question, mais j'ai un doute assez similaire.



void print(int n) {
  if (n < 0) return;
  cout << " " << n;
// The last executed statement is recursive call
  print(n-1);
  print(n-1);
}

Cette queue est-elle récursive?

Question 6

La récursivité de la queue est l'optimisation effectuée par les compilateurs modernes appelés élimination des appels de queue. Lorsque l'appelant / parent ne doit rien faire dans les étapes de détention après la fin des appels d'enfants, la dernière chose est l'appel de récursivité lui-même, le compilateur moderne utilise le goto et les étiquettes pour l'optimisation.

Exemple: Notre version -> imprime n à 1

void fun(int n){
if(n==0)
return;
printf("%d\n",n);
fun(n-1)
}

Après optimisation->

void fun(int n){
start:
if(n==0)
return;
printf("%d\n",n);
n=n-1;
goto start;
}

Avantages de cette optimisation: 1. utilise très peu de programmes de pile pour les appels de la queue réécursive 2.Conse moins de mémoire 3. n'a pas besoin d'enregistrer l'enregistrement d'activation de la procédure, cela réduit la fonction de fonction. 3. Aucun défaut de segmentation plus de segmentation n'est C / C ++ et le débordement de pile en Java.