J'ai lu sur Erlang dernièrement et comment la récursion de la queue est tellement utilisée, en raison de la difficulté d'utiliser des boucles itératives.
Ce n'est pas cette utilisation élevée de la récursion ralentissée, qu'avec tous les appels de fonction et l'effet qu'ils ont sur la pile? Ou la récursion de la queue nie-t-elle la plupart de cela?
5 Réponses :
La récursion de la queue itérative est généralement mise en œuvre avec appels queue . Ceci est fondamentalement une transformation d'un appel récursif vers une boucle simple.
C # Exemple: p> à p> 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;
}
Votre première fonction n'est pas récursive de la queue, de sorte que cela ne sera pas transformé en itération à Erlang.
Vous êtes essentiellement juste, mais un bon compilateur devrait pouvoir voir la structure. Je modifierai mon exemple plus tard.
+ Notez que les deux dernières actions avant le saut de saut sont directement dérivées de l'appel de la queue.
Ajout d'un exemple de queue réel récursif.
Presque tous les compilateurs n'offrent pas la fonction de puissance. Je suis à peu près sûr que Erlang ne le fait pas, alors ne comptez pas dessus!
Complètement vrai. Ce serait un projet intéressant d'écrire un précompiler pour faire ce genre de choses.
Le point est que Erlang optimise des appels queue (non seulement une récursion). L'optimisation des appels de la 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 sur la pile d'appels de fonction en haut de la fonction d'appel, mais le cadre de pile de la fonction en cours est. remplacé par l'une des fonctions appelées. Cela signifie que les appels de la queue n'apportent pas à la taille de la pile.
Donc, non, à l'aide de la récursion de la queue ne ralentit pas erlang down, ni un risque de débordement de pile.
Avec l'optimisation de l'appel de la queue en place, vous pouvez non seulement utiliser une récursion simple de la queue, mais aussi une récursion mutuelle de la queue de plusieurs fonctions (un appels de queue B, quels appels de queue C, quels appels de queue ...). Cela peut parfois être un bon modèle de calcul.
Cela ne devrait pas affecter la performance dans la plupart des cas. Ce que vous recherchez n'est pas que des appels de queue, mais une optimisation de l'appel de la queue (ou une élimination de l'appel queue). L'optimisation des appels quotidiennes est une technique de compilateur ou d'exécution qui figure lorsqu'un appel à une fonction est l'équivalent de «apparition de la pile» pour revenir à la fonction appropriée au lieu de simplement revenir. En règle générale, l'optimisation des appels quotidienne 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.
Une optimisation similaire qui sépare les appels de fonction de texte du programme des appels de fonction de mise en œuvre est "Inlinge". Dans les appels de fonctions de langues modernes / réfléchies, les appels ont peu de lien avec les appels de fonction de niveau de la machine.
Il y a un problème relatif à la récursion de la queue, mais il n'est pas lié à la performance - l'optimisation de la récupération de la queue Erlang implique également l'élimination de la trace de la pile pour le débogage.
Par exemple Voir le point 9.13 de la Erlang FAQ : P>
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.
Perdre la pile est aussi agaçante que de déboguer une boucle d'état étalée: vous n'avez pas accès à l'état des variables de l'itération précédente de la boucle. (En fait des boucles d'état et des TCO ont commencé à me regarder l'équivalent.)