Comment fonctionne exactement la récursion de queue ?

Question

Je comprends presque comment fonctionne la récursion de queue et la différence entre elle et une récursion normale. I seulement ne comprennent pas pourquoi n'a pas nécessite une pile pour se souvenir de son adresse de retour.

// tail recursion
int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

int factorial (int n) {
    return fac_times (n, 1);
}

// normal recursion
int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

Il n'y a rien à faire après avoir appelé une fonction elle-même dans une fonction de récursion de queue mais cela n'a pas de sens pour moi.

Answer 1

Le compilateur est simplement capable de transformer cette

int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

en quelque chose comme ça :

int fac_times (int n, int acc) {
label:
    if (n == 0) return acc;
    acc *= n--;
    goto label;
}

Answer 2

Vous demandez pourquoi "il n'est pas nécessaire que la pile se souvienne de son adresse de retour".

Je voudrais renverser la situation. C'est fait utiliser la pile pour se souvenir de l'adresse de retour. L'astuce est que la fonction dans laquelle la récursion de queue se produit a sa propre adresse de retour sur la pile, et quand elle saute à la fonction appelée, elle la traitera comme sa propre adresse de retour.

Concrètement, sans optimisation des appels de queue :

f: ...
   CALL g
   RET
g:
   ...
   RET

Dans ce cas, lorsque g est appelé, la pile ressemblera à :

   SP ->  Return address of "g"
          Return address of "f"

D'autre part, avec l'optimisation des appels de queue :

f: ...
   JUMP g
g:
   ...
   RET

Dans ce cas, lorsque g est appelé, la pile ressemblera à :

   SP ->  Return address of "f"

Il est clair que lorsque g revient, il retournera à l'endroit où f a été appelé.

EDIT : L'exemple ci-dessus utilise le cas où une fonction appelle une autre fonction. Le mécanisme est identique lorsque la fonction s'appelle elle-même.

Answer 3

La récursion de queue peut généralement être transformée en boucle par le compilateur, en particulier lorsque des accumulateurs sont utilisés.

// tail recursion
int fac_times (int n, int acc = 1) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

se compilerait en quelque chose comme

// accumulator
int fac_times (int n) {
    int acc = 1;
    while (n > 0) {
        acc *= n;
        n -= 1;
    }
    return acc;
}

Answer 4

Il y a deux éléments qui doivent être présents dans une fonction récursive :

1. L'appel récursif
2. Un endroit pour garder le compte des valeurs de retour.

Une fonction récursive "régulière" garde (2) dans le cadre de la pile.

Les valeurs de retour dans une fonction récursive régulière sont composées de deux types de valeurs :

• Autres valeurs de retour
• Résultat du calcul de la fonction propriétaire

Reprenons votre exemple :

int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

Le cadre f(5) "stocke" le résultat de son propre calcul (5) et la valeur de f(4), par exemple. Si j'appelle factorial(5), juste avant que les appels de la pile ne commencent à s'effondrer, j'ai.. :

 [Stack_f(5): return 5 * [Stack_f(4): 4 * [Stack_f(3): 3 * ... [1[1]]

Remarquez que chaque pile stocke, en plus des valeurs que j'ai mentionnées, toute la portée de la fonction. Ainsi, l'utilisation de la mémoire pour une fonction récursive f est O(x), où x est le nombre d'appels récursifs que je dois faire. Donc, si j'ai besoin de 1kb de RAM pour calculer la factorielle(1) ou la factorielle(2), j'ai besoin de ~100k pour calculer la factorielle(100), et ainsi de suite.

Une fonction récursive de queue met (2) dans ses arguments.

Dans une récursion de queue, je passe le résultat des calculs partiels dans chaque cadre récursif au suivant en utilisant des paramètres. Voyons notre exemple de factorielle, Tail Recursive :

int factorial (int n) {
    int helper(int num, int accumulated)
        {
            if num == 0 return accumulated
            else return helper(num - 1, accumulated*num)
        }
    return helper(n, 1)    
}

Regardons ses cadres dans factorial(4) :

[Stack f(4, 5): Stack f(3, 20): [Stack f(2,60): [Stack f(1, 120): 120]]]]

Vous voyez les différences ? Dans les appels récursifs "ordinaires", les fonctions de retour composent récursivement la valeur finale. Dans la récursion de queue, elles ne font référence qu'au cas de base (le dernier évalué). . Nous appelons accumulateur l'argument qui garde la trace des anciennes valeurs.

Modèles de récursion

La fonction récursive régulière est la suivante :

type regular(n)
    base_case
    computation
    return (result of computation) combined with (regular(n towards base case))

Pour le transformer en une récursion Tail nous :

• Introduire une fonction d'aide qui transporte l'accumulateur.
• exécuter la fonction d'aide à l'intérieur de la fonction principale, avec l'accumulateur réglé sur le cas de base.

Regardez :

type tail(n):
    type helper(n, accumulator):
        if n == base case
            return accumulator
        computation
        accumulator = computation combined with accumulator
        return helper(n towards base case, accumulator)
    helper(n, base case)

Vous voyez la différence ?

Optimisation de l'appel de queue

Puisqu'aucun état n'est stocké sur les cas non frontaliers des piles Tail Call, ils ne sont pas si importants. Certains langages/interprètes remplacent alors l'ancienne pile par la nouvelle. Ainsi, sans trame de pile limitant le nombre d'appels, les appels de queue se comportent comme une boucle for. dans ces cas.

C'est à votre compilateur de l'optimiser, ou pas.

Answer 5

Voici un exemple simple qui montre le fonctionnement des fonctions récursives :

long f (long n)
{

    if (n == 0) // have we reached the bottom of the ocean ?
        return 0;

    // code executed in the descendence

    return f(n-1) + 1; // recurrence

    // code executed in the ascendence

}

La récursion de queue est une fonction récursive simple, où la récurrence est faite à la fin de la fonction, donc aucun code n'est fait en ascendance, ce qui aide la plupart des compilateurs de langages de programmation de haut niveau à faire ce qui est connu sous le nom de Optimisation de la récursivité de la queue a également une optimisation plus complexe, connue sous le nom d'optimisation de l'accès aux données. Récursion de la queue modulo