Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 6 of 6

Thread: Factorial

  1. #1
    Regular Coder
    Join Date
    Oct 2011
    Posts
    106
    Thanks
    12
    Thanked 0 Times in 0 Posts

    Factorial

    I have a program that uses recursion to determine the factorial of a number:
    Code:
    #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)?

  • #2
    New Coder
    Join Date
    Aug 2012
    Location
    Odessa, Ukraine
    Posts
    16
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Yeah, you'll have to use some array-based implementation of a 'big number' concept. For example Matt McCutchen's C++ implementation.

  • Users who have thanked Bismark for this post:

    panzertech (08-21-2012)

  • #3
    New Coder
    Join Date
    Jul 2012
    Location
    Ukraine
    Posts
    71
    Thanks
    1
    Thanked 18 Times in 17 Posts
    Also note that recursion is not a good way to calculate the factorial. It's better to use an iterating structure.

  • #4
    New Coder
    Join Date
    Aug 2012
    Location
    Odessa, Ukraine
    Posts
    16
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Quote Originally Posted by oneguy View Post
    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.

  • #5
    New Coder
    Join Date
    Jul 2012
    Location
    Ukraine
    Posts
    71
    Thanks
    1
    Thanked 18 Times in 17 Posts
    Quote Originally Posted by Bismark View Post
    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.

  • #6
    Regular Coder
    Join Date
    Oct 2011
    Posts
    106
    Thanks
    12
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by oneguy View Post
    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?


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •