PDA

View Full Version : Factorial

Scriptr
08-10-2012, 04:43 AM
I have a program that uses recursion to determine the factorial of a number:

#include <iostream>

using namespace std;

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

int main(int argc, char** argv){
unsigned long num;
if(argc >= 2)
num = strtoul(argv[1], NULL, 10);
else{
cout << "Number to be tested: ";
cin >> num;
}

cout << factorial(num) << endl;

return 0;
}

However, I have run into a problem: overflow. 100! exceeds the max value of unsigned long. Is there a larger variable type I could use? Should I use a different method (involving strings, perhaps)?

Bismark
08-14-2012, 12:55 PM
Yeah, you'll have to use some array-based implementation of a 'big number' concept. For example Matt McCutchen's C++ implementation (https://mattmccutchen.net/bigint/).

oneguy
08-14-2012, 03:17 PM
Also note that recursion is not a good way to calculate the factorial. It's better to use an iterating structure.

Bismark
08-14-2012, 03:43 PM
Also note that recursion is not a good way to calculate the factorial. It's better to use an iterating structure.

Factorial calculation is one of the simplest tasks to learn and understand recursion. I think that this is the case.

Also, a lot of compilers support tail recursion optimization.

oneguy
08-14-2012, 04:56 PM
Factorial calculation is one of the simplest tasks to learn and understand recursion.
I agree. Probably the simplest example where recursion is really needed is too complicated. But the OP wants to calculate the factorial for big arguments, so if resursion is used, the call stack will grow significantly compared to the solution without recursion.

Also, a lot of compilers support tail recursion optimization.
Tail recursion optimization isn't applied here because the inner call to the factorial function isn't the last action - the result is multiplied by n after the call.

Scriptr
08-19-2012, 04:12 AM
Also note that recursion is not a good way to calculate the factorial. It's better to use an iterating structure.

@All: I apologize for abandoning this thread. I usually don't get an answer if I don't get one in the first couple of days, so I waited a while, doing some research of my own.

@oneguy: I have not found any non-recursive method to find a factorial. I am by no means asking for a code snippet, but if that is easier, not for this problem (and I am aware that it seems like that), but could you give me an example (or a link that isn't in the first 3 pages of google results) of what you mean?