Using Factorials in C++

[zapshe]

Sorry to post so much, but there's so much I don't know ! When using factorials in C++, I've seen dozens of posts of factorial coding, but I don't understand any of it. A lot of the time I'll see a variable being used like this "factorial *=x". But I don't understand what the * does (Multiplication?) or how it keeps the program multiplying until it reaches 1. Can someone show me code that does actually do factorials and then go over it ? This is currently my calculator so far - with "factorial" blank.

#include "stdafx.h"

#include <iostream>
#include <string>
#include <cmath>
#include <iomanip>


double a;
double x;
double y;
char z;

int subtract()
{
	a = x - y;
	return a;
}

int add()
{
	a = x + y;
	return a;
}

int divide()
{
	a = x / y;
	return a;
}

int multiply()
{
	a = x * y;
	return a;
}

int power()
{
	a = pow(x, y);
	return a;
}

unsigned long long factorial()
{
	return 0; //This is here so the code will compile until I figure this out!
}


int main()
{
	std::cout << "Type In Equation: ";

	std::cin >> x; 
	std::cin >> z;
	if (z == '!')
	{
		goto Operation;
	}
	std::cin >> y;


if (std::cin.fail())
	{
		std::cout << "Not A Number" << std::endl;
		return (0);
	}
	
Operation:
	switch (z)
	{
	case '-':
		subtract();
		std::cout << "The Sum Is: " << std::setprecision(7) << a << std::endl;
		break;
	case '+':
		add();
		std::cout << "The Sum Is: " << std::setprecision(7) << a << std::endl;
		break;
	case '/':
		if (x == 0)
		{
			std::cout << "Not Possible" << std::endl;
			break;
		}
		divide();
		std::cout << "The Sum Is: " << std::setprecision(7) << a << std::endl;
		break;
	case '*':
		multiply();
		std::cout << "The Sum Is: " << std::setprecision(7) << a << std::endl;
		break;
	case '^':
		power();
		std::cout << "The Sum Is: " << std::setprecision(7) << a << std::endl;
		break;
	case '%':
		if (x < y)
		{
			std::cout << "Not Applicable" << std::endl;
		}
		else
		{	// Won't Work If Not Placed Here. Can't Perform % With Anything But Integers.
			int b = x;
			int c = y;
			a = b % c;
			std::cout << "The Remainder is: " << a << std::endl;
		}
		break;
	case '!':
	{
		factorial();
		std::cout << "The Factorial Is: " << a << std::endl;
		break;
	}
	default:
		std::cout << "Unknown Operation: '" << z << "'\n";
	}
	system("pause");
	return 0;
}

[JLBorges]

#include <iostream>

// we assume that the result is within the range of unsigned long long
unsigned long long factorial( unsigned int n )
{
    if( n < 2 ) return 1 ; // factorial(0) == factorial(1) == 1
    else return n * factorial(n-1) ; // eg. factorial 8 = 8 * 7!
}

// we assume that the result is within the range of unsigned long long
unsigned long long factorial_noisy_version( unsigned int n )
{
    unsigned long long result = 1 ;
    std::cout << result ;

    // we keep multiplying the result with numbers 2, 3, 4 ... up to n
    for( unsigned int i = 2 ; i <= n ; ++i )
    {
        std::cout << '*' << i ;
        result *= i ;
    }

    std::cout << " == " << result << '\n' ;
    return result ;
}


int main()
{
    std::cout << factorial(8) << '\n' ;

    factorial_noisy_version(8) ;
}

[zapshe]

Thanks for the detailed reply. The second one is a lot "noisier" than the first! Now, my only question is how the last line n* factorial(n-1) makes a loop. I understand what the line does ( it makes a loop by multiplying the original number with the number 1 less than it then continues to loop in that fashion ), but I don't understand WHY it does it. To me, it looks like it should simply multiply n with n-1 and then be done. If you could explain in greater detail that line of code, it would be greatly appreciated. Thanks !

[JLBorges]

> To me, it looks like it should simply multiply n with n-1 and then be done.

n * factorial(n-1) multiplies n with the result of evaluating factorial(n-1)
So, factorial() is a function that calls itself.

factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1)
Finally, factorial(1) does not need to call factorial() to compute the factorial of a smaller number;
the recursive calls bottom out when n == 1; factorial(1) returns 1

Read the first part of this article for a simple introduction to recursion.
https://www.ibm.com/developerworks/library/l-recurs/

Then, run this noisy version of the recursive implementation of factorial:

#include <iostream>
#include <string>

int recursion_depth = 0 ;

// print recursion_depth*4 spaces, and then the current value of recursion_depth
// return stdout (std::cout)
// it is not important that you understand all about this function right now; its only purpose
// is to indent the output to make viasualisation of the recursive calls easier.
std::ostream& indented( /* std::ostream& stm = std::cout */ )
{ return std::cout << std::string( recursion_depth*4, ' ' ) << recursion_depth << ". " ; }

// we assume that the result is within the range of unsigned long long
unsigned long long factorial( unsigned int n )
{
    ++recursion_depth ;
    indented() << "compute factorial(" << n << ")\n" ;

    unsigned long long result ;

    if( n < 2 )
    {
        indented() << "the recursion bottoms out when n == 1\n" ;
        result = 1 ;
    }
    else
    {
        indented() << "factorial(" << n << ") == " << n << " * factorial(" << n-1 << ")\n" ;
        unsigned long long fn1 = factorial(n-1) ;
        indented() << "factorial(" << n << ") == " << n << " * " << fn1 << '\n' ;
        result = n * fn1 ;
    }

    indented() << "factorial(" << n << ") == " << result << '\n' ;

    --recursion_depth ;
    return result ;
}

int main()
{
    recursion_depth = 0 ;
    factorial(3) ;

    std::cout << "\n----------------------------\n\n" ;

    recursion_depth = 0 ;
    factorial(5) ;

    std::cout << "\n----------------------------\n\n" ;

    recursion_depth = 0 ;
    factorial(12) ;
}

http://coliru.stacked-crooked.com/a/e6220b211a71ee79

[jonnin]

Learning recursion is great, and factorial is an excellent example to approach the subject.

they are also a great candidate for a lookup table solution:

unsigned long long factorial[] = {1,1,2,6,24,120}; //fill it out as far as you like
...
z = fact[5];

etc.

[zapshe]

Sorry to not reply sooner. I must have been very tired when looking over the code, I understand it better now. However, I have a few more questions now. ( I did look at the ibm.com link, but I always find that my questions haven't been answered or the reasoning has flown above my head ).

Firstly, the code seemingly does 2 things at once. Once the program starts and the multiplication begins, does it multiply n * n-1 first or does it call the function first? For example, if we wanted the factorial of 5, would it be 5 * 5-1 first or would that multiplication be put on "hold" until it finishes running through the function loop until it meets the condition of "n == 1"? So simply, would the program do multiplication as it's looping or once it's done looping and has all the numbers needed to multiply? I think the latter cause is the most probable.

Secondly, what stops the function from giving you the answer as "1" for whatever factorial looked for? What I mean is that there's an if function stating that when the variable is less than two, then the function should return 1. But when the function loops, it will always eventually hit one, yet the answer never comes out as "1", why?

Here is my code for factorials after a bit or variable changing to fit my calculator :

unsigned long long factorial(unsigned int x)
{

	if (x < 2) return a = 1;
	else return a = x * factorial(x - 1);

}

With this code, a is what gets displayed as the answer once the function is done and returns the final solution. The question though is why doesn't the answer come out as 1 even thought the function will always eventually have x<2 which should make the function send out the answer as 1. Moreover, how does it not make the answer always come out as 1 but instead makes the function stop when x = 1 ?

Last Question : When typing in a negative number, the console will freak out. For example -5! will not compute. How come it doesn't give an answer of 1? - Even though there's an if function saying if x > 1 then a = 1 ? Thanks for all the help.

[keskiverto]

Get rid of the global variables. You don't want to touch them in your recursive function.

If you do want to store the (unsigned long long) result in your (double) a, then do it in the calling function:

a = factorial( x );
std::cout << "The Factorial Is: " << a << std::endl;
break;

Hence,

unsigned long long factorial(unsigned int n)
{
	if (n < 2) return 1;
	else return n * factorial(n - 1);
}

Did you look at the output of "noisy version" by JLBorges? The should reveal quite a lot.


Trivia question:

unsigned int foo = -5;
// what is the value of foo? 

If you can answer that, then you know that the console does not actually "freak out", but is feverishly computing your desired factorial.

[JLBorges]

> does it multiply n * n-1 first or does it call the function first?

That is not the way that this program works; it multiplies n by the value of (n-1)!
ie. factorial(8) == 8 * 7!

To compute the value of the expression n * factorial(n-1),
the value of the two operands n and factorial(n-1) must be computed

To compute the value of factorial(n-1), the value of n-1 must be computed.

So the steps involved in computing the value of n * factorial(n-1) are:

a. trivially compute the value of n

b i. compute the value of n-1

b ii. compute the value of factorial(n-1) ie. call the function and get its result

c. multiply the value computed in step a with the value computed in step b ii

Note that the final step c. can be done only after step b. ii has been completed



> what stops the function from giving you the answer as "1" for whatever factorial looked for?

A function returns to its caller.

Say, we factorial(3) from main(), factorial(3) calls factorial(2), and factorial(2) calls factorial(1).

The value returned by factorial(1) is returned to its call site in factorial(2).

Strongly consider actually running the program posted earlier, here:
http://www.cplusplus.com/forum/beginner/233172/#msg1048550
and studying its output.


Teaser:
All of the above is subject to the "as-if" rule: the observable behaviour of the program would be "as-if" the control flow was exactly the same as described above.

#include <cmath>

static unsigned long long  factorial( unsigned int n ) 
{ return n < 2 ? 1 : n * factorial(n-1) ; }

// gamma function see: https://en.wikipedia.org/wiki/Gamma_function
// std::tgamma: http://en.cppreference.com/w/cpp/numeric/math/tgamma 
// std::llround: http://en.cppreference.com/w/cpp/numeric/math/round
static unsigned long long  factorial_exotic( unsigned int n ) 
{ return std::llround( std::tgamma(n+1) ); }

unsigned long long foo() 
{ 
    if( factorial_exotic(5) == factorial(7) / 168 * 4 )
        return factorial(7) + factorial_exotic(6) / factorial(4) ;
        
    else return 98765432 ;
    
    // The as-if rule: Allows any and all code transformations that 
    // do not change the observable behavior of the program
    // http://en.cppreference.com/w/cpp/language/as_if
    //
    // the code generated is "as-if" we had written the one liner:
    // return 5070 ;
    //
    // because 
    // a. the condition in the if statement would always be true
    //      5!  ==   7! / (7*6)    ==   7! / 42    ==    ( 7! / 168 ) / 4
    // b. 7! + 6! / 4! == 5040 + 720/24 == 5040 + 30 == 5070
}

https://godbolt.org/g/5DEjEH

[zapshe]

Thanks a lot! I understand now, and I ran the program you showed me, gave me a deeper understanding. But now I have some more questions, sorry! Hopefully these will be the last.

1. If I understood correctly, every time the program runs it returns n * factorial(n-1) until finally n becomes "1" - then it stops from the "if" rule. And the reason when it becomes 1 it doesn't send a = 1 to the is because (didn't know quite how to explain it so hope it's understandable) the function returns that value back to ITS caller instead of the original call to the factorial function? Meaning every time it computes "a" (in my code that returns a in the end), it sends the value of "a" its caller, which would be factorial(2) ? Hopefully I understood that correctly.

2. Why don't negative numbers work? If I put, for example, -5!, the whole program will want to close. However, shouldn't negative numbers be covered in the if statement since negative numbers are less than 2?

Thanks for all the help, it's really appreciated!

[JLBorges]

> the function returns that value back to ITS caller instead of the original call to the factorial function?

Yes. Always, a function returns to its immediate caller.


> Why don't negative numbers work? shouldn't negative numbers be covered in the if
> statement since negative numbers are less than 2?

The function unsigned long long factorial( unsigned int n )
interprets the value passed to it as a non-negative value.

If we write the function as unsigned long long factorial( /* signed */ int n ),
we would get the behaviour that you expect.

[jonnin]

I am not sure that negative factorials are a thing in math. You can make up a definition that fits a purpose, eg return -1*fact(abs(x)) or ??? something else but I don't think classical mathematics defines it: http://mathforum.org/library/drmath/view/60851.html

[icy1]

fun little gotcha with unsigned -- if your function signature is unsigned but you give it a negative number, that input wraps around to fit in the range of unsigned int, so if that range is 0 to 4294967295, the -5 turns into 4294967291, I believe.

The recursive factorial() function would crash because of a Stack Overflow -- many function calls are stacked in memory and only resolve once the base case is reached or until out of memory.

if (n<2) return 1; is the "base case" by the way, an essential first step of designing a recursive function. The second, iterative, solution, is preferred to recursion.

[zapshe]

Thanks a lot everyone for the answers. And yes, negative factorials aren't a thing, but C++ code doesn't know that ! With that in mind, I wanted to be sure the calculator wouldn't answer 1 for any negative factorials. Hence how I saw that the console would want to crash - But it's fixed now.

Thanks especially to JLBorges - You've been a huge help and allowed me to better understand the code I write. Thanks !