J'étudiais à propos de la récupération de l'appel de la queue et je suis tombé sur une documentation mentionnée. Sun Java ne met pas en œuvre l'optimisation des appels de la queue.
J'ai écrit le code suivant pour calculer le numéro de Fibonacci de 3 manières différentes:
1. itératif
2. Head récursif
3. Tour récursive sur l'exécution de ce programme, j'ai attiré quelques résultats: Spécifications du système: processeur Intel Core 5, Windows XP, 32 bits Java 1.6 Taille de la pile par défaut pour JVM.
4 Réponses :
Pour la première question, qu'est-ce que 2 ^ 50 (ou quelque chose de fermeture)? Chaque numéro n dans une fonction FIB récursive l'appelle deux fois (avant 2). Chacune de ces appels 2 itérations avant, etc., il s'agit de 2 ^ (N-K) de récursivité (K est probablement 2 ou 3).
La 2e question est parce que le deuxième est une récursion norme droite. Au lieu d'aller à la double tête (n-1), (n-2) , il construit simplement de m = 1, m = 2 ... m = n. Chaque étape du chemin, la valeur N-1 est conservée pour l'addition. Comme il s'agit d'une opération O (n), elle est comparable à la méthode itérative, la seule différence étant la manière dont le compilateur JIT l'optimise. Le problème avec la récursivité est que cela nécessite une énorme empreinte de mémoire pour chaque niveau que vous empilez sur le cadre - vous manquez d'espace de mémoire ou de pile à une limite. il devrait toujours être généralement plus lent que la méthode itérative.
Oui, je suis d'accord, les valeurs sont méfiantes.
Donc, cela signifie que Java n'a pas fait d'optimisation. La méthode de la queue récursive a pris O (n) qui est identique à la méthode itérative.
Optimisation en termes d'utilisation de la pile. Certaines langues prennent en charge les optimisations d'appel queue qui remplacent les appels récursif de la queue avec des instructions de saut et enregistrant des erreurs de dépassement de pile.
@Ttp - Stephen C a la réponse
En ce qui concerne le point 1: calculer les numéros de fibonacci de calculer récursivement sans mémoisation conduit à un temps d'exécution exponentiel dans n code>. Cela vaut pour tout langage de programmation qui ne signifie pas automatiquement les résultats de la fonction (telles que la plupart des langues non fonctionnelles ordinaires, par exemple Java, C #, C ++, ...). La raison en est que les mêmes fonctions seront appelées encore et encore - par exemple. f (8) code> appelle f (7) code> et f (6) code>; f (7) code> appelle f (6) code> et f (5) code>, de sorte que f (6) code> est appelé deux fois. Cet effet se propage et provoque une croissance exponentielle du nombre d'appels de fonction. Voici une visualisation dont les fonctions sont appelées: f(8)
f(7)
f(6)
f(5)
f(4)
...
f(3)
...
f(4)
...
f(5)
f(4)
...
f(3)
...
f(6)
f(5)
...
f(4)
...
Merci AMOFND. Vous avez raison. La méthode donc récursive a une durée de fonctionnement de O (C ^ N) qui augmente de manière exponentielle comme n augmente.
@TTP: Oui. Cependant, cet effet n'est pas vraiment dû à la récursion de la tête, mais au fait que la méthode récursive s'appelle elle-même deux fois , et que cela finit par être appelé plusieurs fois pour la même valeur d'argumentation et que Il "oublie" quelles valeurs il a déjà calculé. Si vous utilisez Mémoisation , vous obtenez une exécution linéaire.
Cela signifie-t-il que Java fait une optimisation de l'appel de la queue en interne?
Non, ce n'est pas le cas. Les compilateurs Hotspot Jit ne mettent pas en œuvre l'optimisation des appels de queue.
Les résultats que vous observez sont typiques des anomalies que vous voyez dans une référence Java qui ne tient pas compte de l'échauffement JVM. Par exemple, les "premières" fois une méthode sont appelées, elle sera exécutée par l'interprète. Ensuite, le compilateur JIT compilera la méthode ... et il sera plus rapide.
Pour obtenir des résultats significatifs, placez une boucle autour du tout et courez-la plusieurs fois jusqu'à ce que les horaires se stabilisent. Ensuite, jetez les résultats des premiers itérations.
... pourquoi je l'ai fait donner Stackoverflowerror à N> 5000?
C'est juste des preuves qu'il n'y a pas d'optimisation de la queue d'appel qui se produit.
Vous pouvez utiliser Mémoisation pour éviter la récursion de la tête.
J'ai testé le code suivant , quand n <= 40, cette approche est mauvaise parce que la carte dispose d'un compromis. lorsque la valeur de n: 44 Utilisation de l'itération:
Temps itératif = 6984 Utilisation de la récursion de la queue:
TEMPS RÉCURSIVE DE LA TEME = 8940 Utilisation de la mémoire de mémoisation:
Mémoisation Temps récursif = 1799949 Utilisation de la récursion:
Temps récursif de tête = 12697568825
@COOLBEANS Si tel est le cas, inscrivez-moi pour ce professeur
Au moins une des implémentations JVM d'IBM effectue une optimisation de la queue si elle est possible. Stackoverflow.com/questions/105834 / ... et publiib.boulder.ibm.com/infocenter/javasdk/v5r0/index.jsp?top ic = / ...
Vous devriez également observer que le
fibonaccirecrsive est pas la tête récursive, et vous l'avez codé pour avoir une complexité différente de celle des deux autres. (Non, cela n'a pas été suspendu. Cela prend juste deux fois de temps pour calculer 51 à 50, Ergo, 1024 fois plus de calculer 60 50.)