Problème: factoriel récursif

Version imprimable

Bonjour à tous!

J'ai un petit problème avec ce bout de code qui calcule les factoriels de 1! à 25!. En effet, 21! affiche un résultat négatif. Je ne comprend pas pourquoi :?

Voici le bout de code que j'utilise :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Factorial 
{ 
  // Evaluate n! 
  public static long factorial(int n) 
  { 
    if (n <= 1)     // base case 
      return 1; 
    else 
      return n * factorial(n - 1); 
  } 
 
  // Simple test program 
  public static void main(String [] args) 
  { 
    for (int i = 1; i <= 25; i++) 
      System.out.println(i + "! = " + factorial(i)); 
  } 
}

Voici l'affichage:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = -4249290049419214848
22! = -1250660718674968576
23! = 8128291617894825984
24! = -7835185981329244160
25! = 7034535277573963776

Merci pour votre aide, ou pour vos suggestions!

Loader

07/09/2008, 09h40
millie

Normal, il y a un dépassement de capacité du type int (qui est grosso modo de taille 2^31 dans les positif). Donc ça repart dans les négatifs.

Si tu veux vraiment calculer les factoriels jusqu'à de grande taille (ce qui n'est en général pas vraiment utile...), il faut utiliser la classe BigInteger.
15/09/2008, 03h20
empire.dev

vous pouvez changer le type int avec les biginterger de java

Citation:

Envoyé par empire.dev

vous pouvez changer le type int avec les biginterger de java

http://java.sun.com/j2se/1.4.2/docs/...igInteger.html
16/09/2008, 14h41
Frifron

Citation:

Envoyé par millie

Normal, il y a un dépassement de capacité du type int (qui est grosso modo de taille 2^31 dans les positif). Donc ça repart dans les négatifs.

C'est ca sauf que la c'est un dépassement de capacité du long donc la valeur maximal dans les positif est 2^63 - 1 soit tout de même plus de 9e18. Tu vas vite mettre ton pc a genou si tu pars loin dans les factoriels...
17/09/2008, 14h53
dinobogan

Citation:

Envoyé par Frifron

C'est ca sauf que la c'est un dépassement de capacité du long donc la valeur maximal dans les positif est 2^63 - 1 soit tout de même plus de 9e18. Tu vas vite mettre ton pc a genou si tu pars loin dans les factoriels...

Non, c'est bien un int qui est utilisé.
17/09/2008, 15h08
Frifron

non c'est un dépassement du long et non d'int. L'overflow se fait sur 64 bits et non 32. Avec un entier signé sur 32 bits , tu peux aller jusqu'a 2^31 - 1 soit 2 milliards et des poussieres. Tu peux calculer sans dépassement un factoriel jusqu'a 12. avec un entier signé sur 64 bits, tu peux aller jusqu'a 20

Code:

return n * factorial(n - 1);

(long) = (int) * (long)

l'opération est sur 64 bits
18/09/2008, 10h25
dinobogan

Désolé, j'avais regardé le paramètre sans faire attention au type de sortie de la méthode :oops: