L'utilisation de beaucoup de récursion de queue à Erlang ralentit-elle?

Question

J'ai lu récemment à propos d'Erlang et de la façon dont la récursion de la queue est si fortement utilisée, en raison de la difficulté d'utiliser des boucles itératives.

Cette utilisation intensive de la récursivité ne la ralentit-elle pas, avec tous les appels de fonction et l'effet qu'ils ont sur la pile? Ou est-ce que la récursivité de la queue annule la plus grande partie de cela?

Answer 1

La récursivité itérative de la queue est généralement implémentée en utilisant Tail calls. Il s'agit essentiellement d'une transformation d'un appel récursif en une simple boucle.

C# exemple:

uint FactorialAccum(uint n, uint accum) { 
    if(n < 2) return accum; 
    return FactorialAccum(n - 1, n * accum); 
}; 
uint Factorial(uint n) { 
    return FactorialAccum(n, 1); 
}; 

à

uint FactorialAccum(uint n, uint accum) { 
start: 
    if(n < 2) return accum; 
    accum *= n; 
    n -= 1; 
goto start; 
}; 
uint Factorial(uint n) { 
    return FactorialAccum(n, 1); 
}; 

ou mieux encore:

uint Factorial(uint n) { 
    uint accum = 1; 
start: 
    if(n < 2) return accum; 
    accum *= n; 
    n -= 1; 
goto start; 
}; 

---

C# pas vrai récursion de queue, c'est parce que la valeur de retour est modifiée , la plupart des compilateurs ne briseront pas ce faire wn dans une boucle:

int Power(int number, uint power) { 
    if(power == 0) return 1; 
    if(power == 1) return number; 
    return number * Power(number, --power); 
} 

à

int Power(int number, uint power) { 
    int result = number; 
start: 
    if(power == 0) return 1; 
    if(power == 1) return number; 
    result *= number; 
    power--; 
goto start; 
} 

Answer 2

Le fait est que Erlang optimise les appels de queue (non seulement récursion). L'optimisation des appels de queue est assez simple: si la valeur de retour est calculée par un appel à une autre fonction, cette autre fonction n'est pas simplement placée dans la pile des appels de fonction au dessus de la fonction appelante remplacé par l'une des fonctions appelées. Cela signifie que les appels de queue ne s'ajoutent pas à la taille de la pile. Donc, non, l'utilisation de la récursion de queue ne ralentit pas Erlang et ne risque pas de provoquer un débordement de pile. Avec l'optimisation des appels de queue en place, vous pouvez non seulement utiliser la récursion de queue simple, mais aussi la récurrence de queue mutuelle de plusieurs fonctions (un appel de queue b, qui appelle c, qui appelle un appel arrière ...) . Cela peut parfois être un bon modèle de calcul.

Answer 3

Cela ne devrait pas affecter les performances dans la plupart des cas. Ce que vous cherchez n'est pas seulement des appels de queue, mais l'optimisation de l'appel de queue (ou l'élimination de la queue). L'optimisation d'appel de queue est une technique de compilateur ou d'exécution qui détermine quand un appel à une fonction est l'équivalent de «sauter la pile» pour revenir à la fonction appropriée au lieu de simplement revenir. Généralement, l'optimisation de l'appel de queue ne peut être effectuée que lorsque l'appel récursif est la dernière opération de la fonction, vous devez donc faire attention.

Answer 4

Une optimisation similaire qui sépare les appels de fonction de texte de programme des appels de fonction d'implémentation est «inline». Dans les langues modernes/réfléchies, les appels de fonction ont peu de rapport avec les appels de fonction au niveau de la machine.

Answer 5

Il existe un problème relatif à la récursivité de queue, mais il n'est pas lié à la performance - L'optimisation de la récurrence de queue Erlang implique également l'élimination de la trace de la pile pour le débogage.

Par exemple, voir le point 9.13 du Erlang FAQ:

Why doesn't the stack backtrace show the right functions for this code: 

     -module(erl). 
     -export([a/0]). 

     a() -> b(). 
     b() -> c(). 
     c() -> 3 = 4.   %% will cause badmatch 

The stack backtrace only shows function c(), rather than a(), b() and c(). 
This is because of last-call-optimisation; the compiler knows it does not need 
to generate a stack frame for a() or b() because the last thing it did was 
call another function, hence the stack frame does not appear in the stack 
backtrace. 

Cela peut être un peu de douleur quand vous frappez un accident (mais il ne va un peu avec le territoire de la programmation fonctionnelle ...)