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

52

Je connais le concept général de récursivité. Je suis tombé sur le concept de récursion de queue tout en étudiant l'algorithme Quicksort. Dans cette vidéo de l'algorithme de tri rapide du MIT à 18h30, le professeur dit qu'il s'agit d'un algorithme récursif de queue. La récursion de la queue n’est pas claire pour moi.

Quelqu'un peut-il expliquer le concept avec un exemple approprié?

Quelques réponses fournies par la communauté SO ici .

Geek
la source
Parlez-nous davantage du contexte dans lequel vous avez rencontré le terme récursion de queue . Lien? Citation?
A.Schulz
@ A.Schulz j'ai mis le lien vers le contexte.
Geek
5
Regardez « Qu'est - ce que la queue-récursion? Sur stackoverflow »
Vor
2
@ajmartin La question est à la limite du débordement de pile, mais résolument en informatique , donc en principe, l' informatique devrait produire de meilleures réponses. Cela n’est pas arrivé ici, mais il est toujours correct de demander à nouveau ici dans l’espoir d’une meilleure réponse. Geek, vous auriez cependant dû mentionner votre question précédente sur SO, afin que les gens ne répètent pas ce qui a déjà été dit.
Gilles 'SO- arrête d'être méchant'
1
Aussi, vous devriez dire quelle est la partie ambiguë ou pourquoi vous n'êtes pas satisfait des réponses précédentes, je pense que si les gens donnent de bonnes réponses, mais qu'est-ce qui vous a amené à la poser à nouveau?

Réponses:

52

La récursion de la queue est un cas particulier de récursivité dans lequel la fonction appelante ne calcule plus après un appel récursif. Par exemple, la fonction

int f (int x, int y) {
  si (y == 0) {
    renvoyer x;
  }

  retourne f (x * y, y-1);
}

est queue récursive (puisque l'instruction finale est un appel récursif) alors que cette fonction n'est pas récursive:

int g (int x) {
  si (x == 1) {
    retourne 1;
  }

  int y = g (x-1);

  retourne x * y;
}

puisqu'il effectue des calculs après le retour de l'appel récursif.

La récursion de la queue est importante car elle peut être mise en œuvre plus efficacement que la récursion générale. Lorsque nous effectuons un appel récursif normal, nous devons insérer l'adresse de retour dans la pile d'appels, puis passer à la fonction appelée. Cela signifie que nous avons besoin d'une pile d'appels de taille linéaire dans la profondeur des appels récursifs. Lorsque nous avons la récursion de la queue, nous savons que dès que nous revenons de l'appel récursif, nous allons revenir immédiatement, afin que nous puissions ignorer toute la chaîne de fonctions récursives et revenir directement à l'appelant initial. Cela signifie que nous n'avons pas du tout besoin d'une pile d'appels pour tous les appels récursifs et que nous pouvons implémenter l'appel final comme un simple saut, ce qui nous permet de gagner de la place.

Matt Lewis
la source
2
vous avez écrit "Cela signifie que nous n’avons pas besoin d’une pile d’appels pour tous les appels récursifs". La pile d'appels sera toujours là, mais l'adresse de retour ne doit pas nécessairement être écrite dans la pile, n'est-ce pas?
Geek
2
Cela dépend dans une certaine mesure de votre modèle de calcul :) Mais oui, sur un vrai ordinateur, la pile d'appels est toujours là, nous ne l'utilisons tout simplement pas.
Matt Lewis
Que se passe-t-il si c'est le dernier appel, mais dans la boucle? Donc, vous faites tous vos calculs ci-dessus, mais certains d'entre eux dans une boucle commedef recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
thed0ctor
13

Simplement dit, la récurrence finale est une récurrence dans laquelle le compilateur pourrait remplacer l'appel récursif par une commande "goto", de sorte que la version compilée n'aura pas à augmenter la profondeur de la pile.

Parfois, la conception d’une fonction queue récursive nécessite la création d’une fonction d’aide avec des paramètres supplémentaires.

Par exemple, ce n'est pas une fonction queue-récursive:

int factorial(int x) {
    if (x > 0) {
        return x * factorial(x - 1);
    }
    return 1;
}

Mais ceci est une fonction queue-récursive:

int factorial(int x) {
    return tailfactorial(x, 1);
}

int tailfactorial(int x, int multiplier) {
    if (x > 0) {
        return tailfactorial(x - 1, x * multiplier);
    }
    return multiplier;
}

parce que le compilateur pourrait réécrire la fonction récursive en une fonction non récursive, en utilisant quelque chose comme ceci (un pseudocode):

int tailfactorial(int x, int multiplier) {
    start:
    if (x > 0) {
        multiplier = x * multiplier;
        x--;
        goto start;
    }
    return multiplier;
}

La règle pour le compilateur est très simple: lorsque vous trouvez " return thisfunction(newparameters);", remplacez-le par " parameters = newparameters; goto start;". Mais cela ne peut être fait que si la valeur renvoyée par l'appel récursif est renvoyée directement.

Si tous les appels récursifs dans une fonction peuvent être remplacés de la sorte, il s’agit d’une fonction récursive.

Viliam Búr
la source
13

Ma réponse est basée sur l'explication donnée dans l'ouvrage Structure et interprétation des programmes informatiques . Je recommande fortement ce livre aux informaticiens.

Approche A: Processus récursif linéaire

(define (factorial n)
 (if (= n 1)
  1
  (* n (factorial (- n 1)))))

La forme du processus pour l' approche A ressemble à ceci:

(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factorial 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120

Approche B: Processus Itératif Linéaire

(define (factorial n)
 (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
 (if (> counter max-count)
  product
  (fact-iter (* counter product)
             (+ counter 1)
             max-count)))

La forme du processus pour l' approche B ressemble à ceci:

(factorial 5)
(fact-iter 1 1 5)
(fact-iter 1 2 5)
(fact-iter 2 3 5)
(fact-iter 6 4 5)
(fact-iter 24 5 5)
(fact-iter 120 6 5)
120

Le processus itératif linéaire (approche B) s'exécute dans un espace constant, même s'il s'agit d'une procédure récursive. Il convient également de noter que, dans cette approche, un ensemble de variables définit l’état du processus à tout moment, à savoir. {product, counter, max-count}. C'est également une technique par laquelle la récursion en queue permet l'optimisation du compilateur.

Dans l'approche A, l'interprète conserve davantage d'informations cachées, qui constituent essentiellement la chaîne des opérations différées.

ajmartin
la source
5

Tail-récursion est une forme de récursion dans laquelle les appels récursifs sont les dernières instructions de la fonction (d'où provient la partie tail). De plus, l'appel récursif ne doit pas être composé avec des références à des cellules de mémoire stockant des valeurs précédentes (références autres que les paramètres de la fonction). De cette façon, nous ne nous soucions pas des valeurs précédentes et un cadre de pile suffit pour tous les appels récursifs; tail-récursion est un moyen d'optimiser les algorithmes récursifs. L'autre avantage / optimisation réside dans le fait qu'il existe un moyen simple de transformer un algorithme récursif en un algorithme équivalent utilisant l'itération au lieu de la récursion. Alors oui, l'algorithme pour le tri rapide est bien récursif.

QUICKSORT(A, p, r)
    if(p < r)
    then
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q–1)
        QUICKSORT(A, q+1, r)

Voici la version itérative:

QUICKSORT(A)
    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        r = q - 1

    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        p = q + 1
Saadtaame
la source