Writing a factorial function in C-CodePudding

My superficial implementation of the factorial function fails generally for number greater then 16.

#include <stdio.h>

int fact(int x){
  if (x==1)
    return 1;
  else
    return (x* fact(x-1));

}
int main() {
  int x;
  scanf("%d", &x);
  printf("%d\n", fact(x));
  
}

Does this depend on the fact that at a certain point of the recursion the integers will not be representable according to sizeof(int)?

CodePudding user response：

More or less but, the limit should not be 16.

When integers are 32 bits large, the highest representable factorial is

fact(12) = 479001600 = 0x1c8cfc00

(next would be fact(13) = 6227020800 = 0x17328cc00)

And for 64 bits integers, the highest representable factorial is

fact(20) = 2432902008176640000 = 0x21c3677c82b40000

(next would be fact(21) = 51090942171709440000 = 0x2c5077d36b8c40000)

16 should be the limit only on a 48 bits system (6 bytes) which AFAIK is uncommon...

CodePudding user response：

So on your average system an int represents 4 bytes.

The maximum signed number representable with this is 2147483647. Values greater than factorial 12 exceed this number, so it won't be able to be stored in 4 bytes.

The fact that it worked up until factorial 16 may indicate that your int represents 6-bytes, which would be rare.

You can choose to take a long, long long or unsigned data type which typically allow you to store larger positive numbers.