Posté par alf .
En réponse au message cc, as et ld.
Évalué à 1.
long int factorielle(int n)
{
if (n<2)
return 1;
else
return n*factorielle(n-1);
}
Le typage est risqué... Pour les grandes valeurs de n, ton programme
n'est plus portable. Explications :
n est de type int, factorielle(n - 1) est de type
long, donc le produit sera de type long (conversions arithmétiques
usuelles, 3.6.1.8 du n1124).
Lorsque n est grand, au point que factorielle(n - 1) est supérieur à
LONG_MAX / n, le produit est donc supérieur à LONg_MAX et
déborde donc le domaine de valeurs de long.
Le type long est signé, le débordement cause donc un comportement
défini par l'implémentation (6.3.1.3 du n1124).
En langage C, un "comportement défini par l'implémentation" doit être documenté par
ton implémentation (compilateur et/ou libc), mais peut être différent d'une implémentation
à l'autre (une autre version du même compilateur étant une autre implémentation,
comme le même compilateur avec des options différentes).
En utilisant un autre type (comme unsigned long, voire long long ou stdint.h si tu l'as sous la main), tu augmentes le domaine où ta fonction est utile, mais la gestion d'erreur doit être implémentée, quel que soit le type.
Proposition (non testée) :
#include <limits.h>
/*
* Retourne la factorielle de n.
* Si la valeur de n! depasse LONG_MAX, la fonction renvoie -1.
*/
long int factorielle(int n)
{
long res = 1;
if (n >= 2)
{
res = factorielle(n - 1);
if (LONG_MAX / n < res || res == -1)
{
/* debordement */
res = -1;
}
else
{
res *= n;
}
}
return res;
}
J'ai juste fait la correction de l'implémentation, mais l'algorithme de calcul
présenté ici (application naïve de l'algorithme par récursion non terminale)
est largement sous-optimal. Je suppose que le côté algorithmique sera étudié
séparément...
# Débordement
Posté par alf . En réponse au message cc, as et ld. Évalué à 1.
long int factorielle(int n) { if (n<2) return 1; else return n*factorielle(n-1); }Le typage est risqué... Pour les grandes valeurs de n, ton programme n'est plus portable. Explications :- n est de type int, factorielle(n - 1) est de type
long, donc le produit sera de type long (conversions arithmétiques
usuelles, 3.6.1.8 du n1124).
- Lorsque n est grand, au point que factorielle(n - 1) est supérieur à
LONG_MAX / n, le produit est donc supérieur à LONg_MAX et
déborde donc le domaine de valeurs de long.
- Le type long est signé, le débordement cause donc un comportement
défini par l'implémentation (6.3.1.3 du n1124).
En langage C, un "comportement défini par l'implémentation" doit être documenté par ton implémentation (compilateur et/ou libc), mais peut être différent d'une implémentation à l'autre (une autre version du même compilateur étant une autre implémentation, comme le même compilateur avec des options différentes). En utilisant un autre type (comme unsigned long, voire long long ou stdint.h si tu l'as sous la main), tu augmentes le domaine où ta fonction est utile, mais la gestion d'erreur doit être implémentée, quel que soit le type. Proposition (non testée) :#include <limits.h> /* * Retourne la factorielle de n. * Si la valeur de n! depasse LONG_MAX, la fonction renvoie -1. */ long int factorielle(int n) { long res = 1; if (n >= 2) { res = factorielle(n - 1); if (LONG_MAX / n < res || res == -1) { /* debordement */ res = -1; } else { res *= n; } } return res; }J'ai juste fait la correction de l'implémentation, mais l'algorithme de calcul présenté ici (application naïve de l'algorithme par récursion non terminale) est largement sous-optimal. Je suppose que le côté algorithmique sera étudié séparément...