Factorials: Iterative vs. Recursive.

[G3PO]

I'm currently trying to make programs that will use an iterative and recursive solution for the factorial using the formula

C(n, r) = n! / (r! * (n-r)!).

I'm going to use the timing code:

#include <sys/time.h>
#include <cstdlib>
using std::cout;
using std::endl;
int main() {
     struct timeval stop, start;
gettimeofday(&start, NULL);
gettimeofday(&stop, NULL);
     cout << "Time: " << stop.tv_usec - start.tv_usec << endl;
     return 0;
}

How do I go about doing this?

[ResidentBiscuit]

Is the time just to see how long your program takes? You have multiple typos in there, by the way.

Solving factorials is pretty easily. You know how to do it on paper, right? Just translate that to code.

[G3PO]

Yes the timing is just to see which solution is quicker when compiled.

And I think what is throwing me off is iterative vs. recursive. I'm not totally sure what the difference is I guess. Factorials on paper are simple. Just the product of all the whole numbers from one to n. I was confused about the formula given, but now I realize that the C(n,r) is just a different way of saying nCr, or the combination formula.

[ResidentBiscuit]

Iterative is just calculating it inside a loop of some kind, ie iterating one at a time until you arrive to your answer. This is the more "natural" way of doing it. This is how you do it on paper.

The other way uses recursion. This is where you have a function that repeatedly calls itself until it hits a base case which will start the process of exiting all the function calls and leave you with an answer. It can seem really bizarre at first, so doing some reading up and looking at/testing some examples of it will help.

Any problem that is solved with iteration can be solved with recursion, and vice versa. Just some problems are better suited for one or the other. I recommend getting a good grasp on both.

I realize that the C(n,r) is just a different way of saying nCr

Depending on where you're at you'll see it written different ways. I learned at nCr, but then another class used C(n,r), and so did my calculator.

[G3PO]

Okay, so before I get the combination part working, I just want to get an iterative version of a standard factorial working (with the timing). Right now I have this.

#include <sys/time.h>
#include <cstdlib>
#include <iostream>

using namespace std;

using std::cout;
using std::endl;
int main() {
     struct timeval stop, start;
	 gettimeofday(&start, NULL);
    
	 //Iterative Version 
    unsigned int factorial(int n)
    {
        int tot = 1;
        int i;
	cin >> n;
        for(i = 1; i <= n; i++) 
        {
           tot *= i;
        }
	
    }
	gettimeofday(&stop, NULL);
    cout << "Time: " << stop.tv_usec - start.tv_usec << endl; 
    return 0;
}

But I'm getting

iter.cpp:15: error: a function-definition is not allowed here before â{â token
iter.cpp:28: error: expected â}â at end of input

I can't figure out what that means.

[ResidentBiscuit]

Well you just declared and defined a function inside of your main function. You can't do that. You can do this one of a two ways:

1) You can declare and define the function above your main function, and then call it passing the appropriate arguments from main,

2) You can declare it above your main function, then define it underneath the main function, and then call it when you want.

Either way, it has to be at least declared before main. You can't be writing functions inside of functions.

You're also missing the return statement on that function.

[G3PO]

Okay. How do I call the function?

[ResidentBiscuit]

By just using it's identifier and passing in the required arguments.

[Stewbond]

#include <sys/time.h>
#include <cstdlib>
#include <iostream>

using namespace std;

using std::cout;
using std::endl;

 //Iterative Version 
unsigned int factorial(int n)
{
	int tot = 1;
	int i;
	cin >> n;
	for(i = 1; i <= n; i++) 
	{
	   tot *= i;
	}

}

int main() {
     struct timeval stop, start;
	 gettimeofday(&start, NULL);
    factorial(10); // Calling the function
	gettimeofday(&stop, NULL);
    cout << "Time: " << stop.tv_usec - start.tv_usec << endl; 
    return 0;
}

[G3PO]

Okay. Well. What I have now seems to work to get the correct answer for the factorial combination. But I still am not quite sure about the time part. The majority of the time it gives me a negative number. Here's what I've got.

#include <sys/time.h>
#include <cstdlib>
#include <iostream>

using namespace std;

using std::cout;
using std::endl;

 //Iterative Version 
unsigned int factorial(int n)
{
    int r, i;
    unsigned long totn = 1;
    unsigned long totr = 1;
    unsigned long totsub = 1;
    unsigned long final;
    cout << "Enter n, r: ";
    cin >> n;
    cin >> r;
    for(i = 1; i <= n; i++) 
    {
        totn *= i;
    }
	for (i = 1; i <= r; i++)
	{
		totr *= i;
	}
	for (i = 1; i <= (n-r); i++)
	{
		totsub *= i;
	}
	final = (totn/(totr * totsub));
	cout << "The total is " << final << ".\n";
}

int main() {
    struct timeval stop, start;
    gettimeofday(&start, NULL);
    
    factorial(10);

    gettimeofday(&stop, NULL);
    cout << "Time: " << stop.tv_usec - start.tv_usec << endl; 
    return 0;
}

[Stewbond]

Wait a sec, I just realized that your function takes parameter n and then waits for a cin>>n.

First, your performance measurements will really only measure the time it takes to cin>>n as your typing will take longer than any computer operation.

Second, the point of passing n as an argument is defeated if you just write to it in the function.

Remember, functions should do their job and ONLY their job. It should calculate the factoral only, not handle inputs. Any additional logic in there will skew your analysis.

Try this instead:

int main() {
    struct timeval stop, start;
    int n;
    cin >> n;
    gettimeofday(&start, NULL);
    factorial(n); // Calling the function
    gettimeofday(&stop, NULL);
    cout << "Time: " << stop.tv_usec - start.tv_usec << endl; 
    return 0;
}

Then

//Iterative Version 
unsigned int factorial(unsigned int n)
{
    int tot = 1;
    for(int i = 1; i <= n; i++) 
        tot *= i;
    return tot;
}

//Recursive Version
unsigned int factoral_recursive(unsigned int n)
{
    if (n < 2) return 1;
    return n*factoral_recursive(n-1);
}

Third, unsigned int only has 32 bits on most systems. That's only going to get you to 12! which is only 12 iterations before overflow. That isn't many calculations to analyze. You could use unsigned long long (64 bits), but that will only get you to 15! For performance analysis, choose something that can handle tons of iterations like a square root, addition, fibinacci sequence, taylor series or something that doesn't explode on us.

[ResidentBiscuit]

Yea factorials get huge very fast, and without a library like bignum you're going to cause errors pretty quickly.

Something you could also test is inline vs not inlined. Though to be honest I'm not sure how an inline recursive function will do. Maybe Stewbond can explain

[G3PO]

I think I need one that will go up to 27 digits, because I'm only supposed to calculate for n = 20, r = 3, and n = 2000, r = 10, and note the timing differences between them.

[Stewbond]

What is r?

n = 2000???? That's rediculous. You'll need some sort of external big-number library for that. (maybe this: http://gmplib.org/)

[G3PO]

"r" is referring to the formula of nCr that I'm supposed to use. The I was using the n! for an example, but I'm actually supposed to be calculating for C(n, r) = n! / (r! * (n-r)!).

[ResidentBiscuit]

2000! = a number with 5736 digits -_-

Does anyone know how WolframAlpha does this? I just plugged it in there and it gave me an answer in a couple of seconds

[G3PO]

Yeah but once it is divided by the second half of the equation it's only 27 digits which seems much more reasonable.

[G3PO]

Well at this point I think I'm okay with what I have for the iterative part. It calculates reasonable combinations and times the function, which is really all I need. I just need to get the recursive part done, which I am not understanding still. Again I'll start with getting the factorial of n, then I can change it to make it the combination. This is what I have.

#include <sys/time.h>
#include <cstdlib>
#include <iostream>

using namespace std;

using std::cout;
using std::endl;
using std::endl;

/* Recursive Version */ 
long factorial(int n){
     if (n == 0) 
	return 1;
     else
     {
	return (n * (factorial(n-1)));
     }
}

int main() {
    struct timeval stop, start;
    int n;
    cout<< "Enter n, r: ";
    cin >> n;
    gettimeofday(&start, NULL);
    
    factorial(n);

    gettimeofday(&stop, NULL);
    cout << "Time: " << stop.tv_usec - start.tv_usec << endl; 
    return 0;
}

If I compile this, it will take my input of n, and then tell me then time and terminate. I must be missing something or not doing the recursion correctly.

[Stewbond]

You're getting exactly what I would have expected. You input the value of n, the computation is done, and you get the output. You're using linux-specific libraries so I can't try this myself, but what kind of numbers are you getting?

You could try something like this to prove that the calculation was done:

int main() {
    struct timeval stop, start;
	int n, output;
	cout<< "Enter n: ";
	cin >> n;

	gettimeofday(&start, NULL);
    
	output = factorial(n);

	gettimeofday(&stop, NULL);
    cout << n << "!: " << output << std::endl << "Time: " << stop.tv_usec - start.tv_usec << endl; 
    return 0;
}

[G3PO]

Interesting. My problem wasn't that it gave wrong numbers, just that it didn't give numbers. Doing it how you suggested does give correct numbers though, so maybe it was just a matter of output.