C Programming Basics
int fact(int n) {
if (n <= 1)
return 1;
return n * fact(n - 1);
}int is 32 bits (maximum 2147483647). Which of the following is the largest n for which the function fact(n) above returns the factorial of n correctly, without overflow?
- A12
- B13
- C20
Show answer and explanation
Answer: A. 12
fact is a recursive function that calls itself as n × fact(n − 1) and returns 1 when n is 1 or less. 12! = 479001600 is less than the int maximum 2147483647, so it is computed correctly, but 13! = 6227020800 exceeds the maximum. In fact(13), signed integer overflow occurs in the final multiplication 13 × 479001600, and that is undefined behavior. For example, unoptimized gcc on x86-64 returns 1932053504, the remainder of 6227020800 modulo 2³², but this result is not guaranteed. For larger n, use the 64-bit long long (up to n = 20) or similar.
- A. Correct. 12! = 479001600 is below the maximum, and 13! exceeds it.
- B. 13! = 6227020800 exceeds the int maximum 2147483647, so it is not computed correctly.
- C. 20 is the largest n computed correctly with a 64-bit signed integer (such as long long).