Comment fonctionne exactement la récursivité de la queue?

Je comprends presque comment fonctionne la récursivité de queue et la différence entre elle et une récursivité normale. je ne comprends pas pourquoi il n'a pas besoin de pile de se rappeler 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écursivité de queue, mais cela n'a aucun sens pour moi.

Le compilateur est simplement capable de transformer cela

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

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

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

Concrètement, sans optimisation des appels de fin:

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

Dans ce cas, lors de l' gappel, la pile ressemblera à:

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

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

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

Dans ce cas, lors de l' gappel, la pile ressemblera à:

   SP ->  Return address of "f"

Clairement, lors du gretour, il retournera à l'endroit d'où il a fé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.

La récursivité 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);
}

compilerait en quelque chose comme

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

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 dé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 la 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 propre

Regardons votre exemple:

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

La trame 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 pile ne commencent à se réduire, j'ai:

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

Notez 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 effectuer. Donc, si j'ai besoin de 1 ko de RAM pour calculer factorielle (1) ou factorielle (2), j'ai besoin d'environ 100 ko pour calculer factorielle (100), et ainsi de suite.

Une fonction Tail Recursive met (2) dans ses arguments.

Dans une récursion de queue, je passe le résultat des calculs partiels dans chaque image récursive à la suivante en utilisant des paramètres. Voyons notre exemple factoriel, Tail Recursive:

int factoriel (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 factoriel (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 "réguliers", les fonctions de retour composent récursivement la valeur finale. Dans Tail Recursion, ils ne font référence qu'au cas de base (le dernier évalué) . Nous appelons accumulator l'argument qui garde la trace des anciennes valeurs.

Modèles de récursivité

La fonction récursive régulière va comme suit:

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

Pour le transformer en une récursivité Tail nous:

• Introduisez une fonction d'assistance qui porte l'accumulateur
• exécutez la fonction d'assistance à 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)

Regarde la différence?

Optimisation des appels de queue

Puisqu'aucun état n'est stocké sur les piles Non-Border-Cases des piles Tail Call, ils ne sont pas si importants. Certaines langues / interprètes remplacent alors l'ancienne pile par la nouvelle. Ainsi, sans cadres de pile contraignant 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 non.

Voici un exemple simple qui montre comment fonctionnent les 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écursivité de la queue est une simple fonction récursive, où la récurrence est effectuée à 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 que l'on appelle l' optimisation de la récursivité de la queue , a également un optimisation plus complexe connue sous le nom de module de récurrence de queue

La fonction récursive est une fonction qui appelle par elle-même

Il permet aux programmeurs d'écrire des programmes efficaces en utilisant une quantité minimale de code .

L'inconvénient est qu'ils peuvent provoquer des boucles infinies et d'autres résultats inattendus s'ils ne sont pas écrits correctement .

Je vais expliquer à la fois la fonction récursive simple et la fonction récursive de queue

Pour écrire une fonction récursive simple

1. Le premier point à considérer est quand devriez-vous décider de sortir de la boucle qui est la boucle if
2. Le second est quel 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 pour sortir de la boucle

else 
     return n * fact(n-1);

Le traitement réel doit-il être effectué

Permettez-moi de rompre la tâche une par une pour une meilleure compréhension.

Voyons ce qui se passe en interne si je cours fact(4)

1. Remplacer n = 4

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

Ifla boucle échoue donc elle va en elseboucle donc elle retourne4 * fact(3)

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

   Remplacer n = 3

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

If la boucle échoue donc il va à elseboucle

donc ça revient 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 mémoire de pile, nous avons 4 * 3 * fact(2)

   Remplacer n = 2

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

Ifla boucle échoue donc elle passe en elseboucle

donc ça revient 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 mémoire de pile, nous avons 4 * 3 * 2 * fact(1)

   Remplacer n = 1

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

If la boucle est vraie

donc ça revient 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 du fait (4) = 4 * 3 * 2 * 1 = 24

La récursion de la queue serait

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

1. Remplacer n = 4

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

Ifla boucle échoue donc elle va en elseboucle donc elle retournefact(3, 4)

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

   Remplacer n = 3

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

Ifla boucle échoue donc elle passe en elseboucle

donc ça revient fact(2, 12)

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

   Remplacer n = 2

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

Ifla boucle échoue donc elle passe en elseboucle

donc ça revient fact(1, 24)

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

   Remplacer 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 vraie

donc ça revient running_total

La sortie pour running_total = 24

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

Ma réponse est plutôt une supposition, car la récursivité est liée à l'implémentation interne.

Dans la récursivité de queue, la fonction récursive est appelée à la fin de la même fonction. Le compilateur peut probablement optimiser de la manière ci-dessous:

1. Laissez la fonction en cours se terminer (c'est-à-dire que la pile utilisée est rappelée)
2. Stocker les variables qui vont être utilisées comme arguments de la fonction dans un stockage temporaire
3. Après cela, appelez à nouveau la fonction avec l'argument stocké temporairement

Comme vous pouvez le voir, nous sommes en train de terminer la fonction d'origine avant la prochaine itération de la même fonction, donc nous n'utilisons pas réellement la pile.

Mais je crois que s'il y a des destructeurs à appeler dans la fonction, cette optimisation peut ne pas s'appliquer.

Le compilateur est suffisamment intelligent pour comprendre la récursivité de la queue. Dans le cas où, lors du retour d'un appel récursif, il n'y a pas d'opération en attente et l'appel récursif est la dernière instruction, tombez dans la catégorie de la récursivité de la queue. Le compilateur effectue essentiellement une optimisation de la récursivité de la queue, en supprimant l'implémentation de la pile.

void tail(int i) {
    if(i<=0) return;
    else {
     system.out.print(i+"");
     tail(i-1);
    }
   }

Après avoir effectué l'optimisation, le code ci-dessus est converti en code ci-dessous.

void tail(int i) {
    blockToJump:{
    if(i<=0) return;
    else {
     system.out.print(i+"");
     i=i-1;
     continue blockToJump;  //jump to the bolckToJump
    }
    }
   }

C'est ainsi que le compilateur effectue l'optimisation de la récurrence de queue.