Laquelle de ces deux méthodes d'obtention d'une factorielle (boucle vs récursive) est plus efficace / plus rapide? Et si cela peut être amélioré, comment?
Langue: Java P>
private static long factrecur(int n) {
if (n == 0) {
return 1;
}
else {
return n * factrecur(n-1);
}
}
private static long factloop(int a) {
long total = 1;
for (int b=a;b>=1;b--) {
total *= b;
}
return total;
}
3 Réponses :
La boucle pour la boucle sera plus efficace car il n'y a pas de frais générale des appels de méthode. (En règle générale, les boucles sont presque toujours plus efficaces que la récursivité)
Pour expliquer pourquoi vous devez entrer dans les détails de Nitty Gritty de ce qui se passe lorsque vous appelez une méthode et quelque chose appelé Call Stack .
Fondamentalement, lorsque vous appelez une méthode, il a besoin d'un peu d'espace pour fonctionner (pour des choses comme ses variables locales, etc.) Il a également besoin d'espace pour les paramètres entrants qui lui sont transmis et un lieu de stockage de l'adresse de retour de l'endroit où elle devrait aller quand il est fait exécuter. Cet espace est fourni de manière dynamique en "poussant" les valeurs sur une pile. Cet espace de pile reste occupé jusqu'à ce que la méthode revienne à quel point il est «sauté».
Pensez donc à la récursion dans ce contexte: chaque fois que vous appelez la méthode de l'intérieur, vous appuyez plus de données sur la pile, sans revenir de la méthode que vous étiez dans (et donc sans libérer l'espace de pile que la méthode d'appel était occupée. ). Au fur et à mesure que votre récursivité va plus loin, la quantité de mémoire augmente.
En revanche, la boucle que vous avez écrite utilise simplement la quantité fixe de la mémoire fournie par une presse-poussée d'une pile.
Bien sûr, sauf si vous utilisez une langue fonctionnelle et un profit de la récursion de la queue.
Un appel sur Long sera envahi par factorial (21) , qui est un petit nombre, pour obtenir un problème de performance significatif. Pour des nombres plus élevés, le code échouera - pour des appels très fréquents, un hashmap sera plus rapide que des boucles répétées. Plusieurs appels sur BigInteger pourraient toujours être plus rapides avec un haschmap derrière la scène. N'oubliez pas: l'optimisation prématurée est la racine de tout mal.
Oui Oui, vous collaborez tous des points extrêmement valables, mais je pense aussi que vous êtes un peu sur les choses en ingénierie. Je soupçonne que Dely ne cherche pas vraiment à trouver le meilleur moyen de calculer les facteurs facteurs mais vraiment à la recherche d'aide avec ses devoirs ...
Oh, il semble que j'ai oublié ce post. La question n'était pas des devoirs, j'apprends Java sur mon propre chef.
Le seul problème avec la récursion est que chaque fois que la fonction est appelée, l'adresse est mise en haut de la pile, concaténant beaucoup d'appel peut provoquer un dépassement de pile
Avec 21 appels, votre longue volonté Vous auriez peut-être besoin de BigInteger pour mesurer une différence significative, lors de la mesure factorielle (10 * 1000 * 1000) ou quelque chose qui est grand. Si vous n'avez pas numéros hauts pour calculer, mais calculez les facteurs faibles souvent , un hashmap avec des valeurs préalculées sera plus rapide que la réursion
+1: Je dirais; Vérifiez que la performance compte avant de vous inquiéter.
Total * = HI; - Qu'est-ce quehi ?Avez-vous compris-vous-vous? Qu'est-ce que cela vous a dit?
Oh désolé Nideo, je renommais les variables sur l'éditeur de texte, j'ai oublié de le changer. Je ne sais pas comment faire référence, mais je vais le regarder.
Plutôt que b> = 1 dire b> 0 comme il y a généralement des instructions de niveau inférieures à comparer avec 0 qui rendra le code plus rapide
Pour les boucles sont certainement meilleurs que la récursion, plus, vous pourriez vous retrouver dans un flux de piquant (aucun jeu de mots intimé :)) dans ce dernier cas en N est très grand.
Dans la boucle, vous n'avez pas besoin de multiplier par 1. Utiliser
; B> 1; suffit.