Help understanding recursive function to compute factorials

[curious noob]

Working through Stroustrup's PPP book. Below is my solution to Chp 6 exercise 10, which is a program for calculating permutations and combinations.

I have two functions for computing factorials. The recursive function doesn't properly recognize when the factorial exceeds int limits. Can you help me understand why?

#include "../std_lib_facilities.h"

int factorial( int n )

{
	int f = 1;
	for( ; n > 0; n--)
        {
		f *= n;
		if ( f < 0 ) error("Factorial too large"); 
                //when number exceeds int limits, it goes into negative range.
	}
	return f;
}

// Original function below. Not sure why this one doesn't check factorial size correctly.
// Returns odd values when computing 13! but hits error on larger numbers like 22!
/*{
    if( n == 0 ) return 1;
    n *= factorial( n - 1 );
    if( n < 1 ) error("Factorial too large"); 
    //when number exceeds int limits, it goes into negative range.
    return n;
}*/

int combinations( int b, int p )
{
    return p / factorial(b);
}

void compute(int a, int b, char ch)
{
    //compute permutations first
    int p; p = factorial(a);  p = p / factorial(a-b);
    if(ch == 'c')
    {
        p = combinations(b,p);
        cout << "\nThere are " << p << " combinations.";
        return; //skip cout below
    }
    cout << "\nThere are " << p << " permutations.";
}

void checkIntInput( int a, int b)
{
    if( a < b ) error("Set cannot have less elements than permutation/combination subset." );
    if( a < 0 || b < 0 ) error("Neither set nor subset can be negative.");
}

int main()
try
{
    long int a,b;
    char ch;
    cout << "Enter two integers for calculating permutations or combinations: ";
    while( cin >> a, cin >> b )
    {
        checkIntInput(a,b);
        cout << "Permutations or combinations? (p/c): ";
        cin >> ch;
        if( ch != 'p' && ch != 'c' ) error("Failed to get p or c.");
        compute(a,b,ch);
        cout << "\n\nEnter two integers or \"|\" to exit: ";
    }
    return 0;
}
catch (exception& e)
{
    cerr << "error: " << e.what() << '\n';
    return 1;
}
catch (...)
{
    cerr << "Oops: unknown exception!\n";
    return 2;
}

[kevinkjt2000]

//when number exceeds int limits, it goes into negative range.

Actually, this is not necessarily true.

0 00011100 10001100 11111100 00000000₂ = 12₁₀!
1 01110011 00101000 11001100 00000000₂ = 13₁₀!

Notice how the sign bit in 13! is actually 0. The overflow bit is probably set, I would have to dig out assembly references and look at the mul or the imul instruction.

The quickest way to solve this problem is just checking if the number is <= 12, because 13! is too large for 32 bit signed or unsigned integers.

Edit: I made a table of integers vs. required number of bits for their factorials

0 1 2 3 4 5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 5 7 10 13 16 19 22 26 29 33 37 41 45 49 53 57 62 66 70 75 80

[Duthomhas]

I don't have the time to really analyze your code very deeply, but the problems all sound to be integer overflow problems.

Line 11 is wrong. You should check for overflow before multiplying:

int factorial( int n )
{
	int f = 1;
        if (n < 0) return 0;  // check for bad n
	for( ; n > 0; n--)
        {
                // Check that the product is in range of the multiplicands
                if (f > std::numeric_limits <int> ::max() / n) 
                        error("Factorial too large"); 
                // All good: do it
		f *= n;
	}
	return f;
}

You can read more here: http://stackoverflow.com/a/1815391/2706707

And like I said, I haven't looked too hard at your combinations/permutations, but using factorial here, while mathematically correct (and simple) is not actually the best choice.

For what you're doing, it's fine. But if you want to really crunch it, you need to choose another algorithm to compute the possibilities.

(One possibility: think about a version of factorial() that also takes a lower limit to stop at, instead of stopping at zero.)

Hope this helps.