Récursion vs boucles For – Factorials, Java

Laquelle de ces deux méthodes pour obtenir une factorielle (boucle vs récursive) est plus efficace / plus rapide? et si cela peut être amélioré, comment alors?

Langue: Java

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; } 

La boucle for sera plus efficace car il n’y a pas de surcharge 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 les plus importants de ce qui se passe lorsque vous appelez une méthode et quelque chose appelé la stack d’appels .

En gros, lorsque vous appelez une méthode, elle a besoin d’un peu d’espace (pour des variables telles que ses variables locales, etc.), elle a également besoin d’espace pour les parameters entrants qui lui sont transmis et d’un emplacement pour stocker l’adresse de retour correspondant c’est fait exécuter. Cet espace est fourni dynamicment en “poussant” les valeurs sur une stack. Cet espace de stack rest occupé jusqu’à ce que la méthode retourne à quel point il est «supprimé».

Pensez donc à la récursivité dans ce contexte: chaque fois que vous appelez la méthode de l’intérieur, vous mettez plus de données dans la stack, sans revenir de la méthode dans laquelle vous vous trouviez (et donc sans libérer de l’espace de stack qu’elle occupait). Plus la récursion est profonde, plus la quantité de mémoire augmente.

En revanche, la boucle for que vous avez écrite utilise simplement la quantité de mémoire fixe fournie par une poussée de trame.

Avec 21 appels, votre longue volonté sera dépassée , ce qui est très tôt pour mesurer une différence, ce qui pourrait devenir pertinent.

Vous aurez peut-être besoin de BigInteger pour mesurer une différence significative lors de la mesure factorial (10*1000*1000) ou de quelque chose d’aussi grand. Si vous n’avez pas de nombres élevés à calculer, mais calculez souvent des factorielles faibles, une table de hachage avec des valeurs précalculées sera plus rapide que la récursivité et la mise en boucle.

Le seul problème avec la récursion est que chaque fois que la fonction est appelée, son adresse est placée en haut de la stack, la concaténation de nombreux appels peut entraîner une exception de débordement de stack si le nombre d’appels de récursivité est élevé.