Comment fonctionne exactement la récursion de la queue?

Je comprends presque comment fonctionne la récursion de la queue et la différence entre celle-ci et une récursivité normale. Je ne comprends pas pourquoi il n’a pas besoin de stack 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 dans une fonction de récursion de la queue, mais cela n’a pas de sens pour moi.

    Le compilateur est tout 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); } 

    dans 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 ne faut pas que la stack se souvienne de son adresse de retour”.

    Je voudrais renverser la situation. Il utilise la stack pour mémoriser 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 stack et lorsqu’elle passe à la fonction appelée, elle la traitera comme étant sa propre adresse de retour.

    Concrètement, sans optimisation de la queue:

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

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

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

    D’un autre côté, avec l’optimisation des appels de queue:

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

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

      SP -> Return address of "f" 

    De toute évidence, lorsque g revient, il retournera à l’endroit d’où l’on a appelé f .

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

    La récursion de la queue peut généralement être transformée en une 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); } 

    comstackr à 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 compte des valeurs de retour.

    Une fonction récursive “régulière” rest (2) dans le cadre de la stack.

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

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

    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 stack ne commencent à s’effondrer, j’ai:

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

    Notez que chaque stack stocke, outre les valeurs que j’ai mentionnées, toute l’étendue 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 j’ai à effectuer. Donc, si j’ai besoin de 1kb de RAM pour calculer la factorielle (1) ou la factorielle (2), il me faut ~ 100k pour calculer la factorielle (100), et ainsi de suite.

    Une fonction récursive Queue (2) dans ses arguments.

    Dans une récursion de la queue, je passe le résultat des calculs partiels dans chaque trame récursive à celui suivant en utilisant les parameters. Voyons notre exemple factoriel, Tail Recursive:

    int factorial (int n) {int helper (int num, int accumulé) {si num == 0 retourne accumulé else retour helper (num – 1, accumulated * num)} return helper (n, 1)
    }

    Regardons ses frames dans factorial (4):

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

    Voir 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 normale 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écursion de queue, nous:

    • Introduire une fonction d’assistance qui porte l’accumulateur
    • exécuter la fonction d’assistance dans la fonction principale, avec l’accumulateur défini 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 d’appel de queue

    Étant donné qu’aucun état n’est stocké dans les cas non-frontaliers des stacks d’appels à la queue, ils ne sont pas si importants. Certains langages / interprètes remplacent alors l’ancienne stack par la nouvelle. Donc, comme il n’y a pas de frameworks de stack limitant le nombre d’appels, les appels de queue se comportent exactement comme une boucle for dans ces cas.

    C’est à votre compilateur de l’optimiser ou non.

    Voici un exemple simple qui montre comment les fonctions récursives fonctionnent:

     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 la queue est une fonction récursive simple, dans laquelle la récurrence est effectuée à la fin de la fonction, donc aucun code n’est effectué en ordre ascendant, ce qui aide la plupart des compilateurs de langages de programmation de haut niveau à faire ce que l’on appelle optimisation plus complexe connue sous le nom de modulo de récursion de la queue

    Ma réponse est plutôt une supposition, car la récursivité est liée à la mise en œuvre interne.

    En récursion de queue, la fonction récursive est appelée à la fin de la même fonction. Probablement que le compilateur peut optimiser de la manière suivante:

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

    Comme vous pouvez le constater, nous terminons la fonction d’origine avant la prochaine itération de la même fonction, nous n’utilisons donc pas réellement la stack.

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

    Le compilateur est assez intelligent pour comprendre la récursion de la queue. Dans le cas où l’on revient 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. Compilateur effectue essentiellement l’optimisation de la récursion de la queue, en supprimant l’implémentation de la stack. Considérez ci-dessous le code.

     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 un.

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

    Voici comment le compilateur effectue l’optimisation de la récursion de la queue.