Factorielle

Le grand pb avec le calcul de la factorielle est lorsque n est très grand. tu peux utiliser listes chaînées pour stocker chacun des chiffres de chaque nombres allant de n à 1.

@julien2011

Lorsque l'on calcule n! la limite sur la taille de n pour obtenir un résultat correct dépend du type de retour de la fonction factorielle.

int    => n<12
long   => n<22
float  => n<34
double => n<170

Mais pour les grandes valeurs de n il n'est pas nécessaire de passer par des listes chaînées car Java implémente déjà des calculs de grands nombres (BigInteger, et BigDecimal)
Le plus gros problème est d'adapter l'algorithme à ces grandes valeurs...

Prenons l'algorithme "naïf" qui calcule n! en faisant n*(n-1)!
Si on utilise l'implémentation récursive on va obtenir des StackOverflowError
Donc on utilisera plutôt l'algorithme itératif mais le temps va être très long...

Exemple d'exécutions avec des BigInteger :
StackOverflowError en récursif pour n>25 000
Temps d'exécution de 15 minutes en itératif pour n=500 000