Geek asks and answers

Recursive factorial function not working properly

Why can this recursive function be evaluated only up to (20!)? When I enter 21, it shows an unexpected result.

#include <iostream>
using namespace std;

long long int factorial( long long int number )
{
    if( number <= 1 )
        return 1;

    return number * factorial( number - 1 );

}

int main()
{
    long long int number;
    while( cin >> number )
            cout << factorial( number ) << endl; // factorial( 20 ) = 2432902008176640000
                                                 // factorial( 21 ) = -4249290049419214848 ????
    return 0;
}
+3
source share
2 answers

Factorial 21 is equal 51090942171709440000. The maximum value 2^63-1 = 9223372036854775807is the signed long long number on your computer.

2432902008176640000    20 factorial
9223372036854775807    2^63-1 (the maximum for a long long on your computer)
51090942171709440000   21 factorial

When the number is greater than the maximum, then the behavior is undefined. What happens on most computers is that it goes around the most negative number.

+6
source

Since the integral long long type has a maximum that it can store. You can get it using the following instructions

#include <iostream>
#include <limits>

int main()
{
    std::cout << std::numeric_limits<long long>::max() << std::endl;
}

long long , 8 .

 0: 1 
 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
+2

More articles:


All Articles