Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C++ Programmer Defined Factorial Function

  1. Feb 27, 2009 #1
    Hi

    I am relatively new to C++ and I am having a little trouble understanding, in detail, the logic
    of this recursive function.

    Can someone tell me if my reasoning this out is correct?

    Code (Text):
    int fact (int n)
    {
        if (n==1)
        return 1;
         
        else
        return (n*fact(n-1));
       
    }
     
    So if the user enters 1, it returns 1. But if the user enters 3... what happens here?

    it returns 3*fact(2)
    and then fact(2) returns 2*fact(1)
    and fact (1)=1
    so we have 3*2*1= 3!

    okay...so I guess I do get it kind of.

    But when it says "return (n*fact(n-1)" where exactly is it "returning" it?

    It seems like it means "return it to the argument of the function".

    Is that more or less correct? Especially what is in boldface...
     
  2. jcsd
  3. Feb 27, 2009 #2
    It's a http://en.wikipedia.org/wiki/Recursion#Recursion_in_computer_science". Not C++ specific thing.

    I understood it by assuming that
    "int fact (int n)" is not equal to "fact(n-1)" i.e. they are two different functions something like

    int fact1 (int n)
    {
    return fact2(n-1);
    }

    int fact2 (int n)
    {
    return something;
    }


    To function or method, there is no difference between calling itself or calling another function..I would say in that line it just calling itself and places the call on the stack.
    In 3 case, it keeps on putting calls on the stack until you return 1:
    func(1) = 1
    func(2)
    func(3)

    func(1) is evaluated which was called by func(2) and is removed from the stack, then func(2) and then func(3)
     
    Last edited by a moderator: Apr 24, 2017
  4. Feb 27, 2009 #3
    Agreed.

    Not sure about all of that. I think the way I wrote it makes more sense..but that's me!


    I guess I just need to know this
    Is it returning it to n?
     
  5. Feb 27, 2009 #4
    noticed your edit. I think that makes some sense to me.
     
  6. Feb 28, 2009 #5
    You might want to use some better word than returning to n. I don't understand "what "returning to n" is. return (n*fact(n-1)) is just equivalent to return (a constant * fact (n-1))
    Whenever fact (n-1) is evaluated and removed from the stack, it returns another constant which is multiplied then by n and then function returns the result.

    I don't know anything more about recursion - just that I need a base case (stopping condition) and other body. You can use it instead of for/while loops (in some cases) if your code looks neater but in my understanding, use recursion only if it make your code look simple.
     
  7. Feb 28, 2009 #6

    rcgldr

    User Avatar
    Homework Helper

    Not quite, the return statement is the value returned when that instance of the function exits. The first return statement, return(3*fact(2)) requires that fact(2) return a value before the expression 3*fact(2) can be evaulated and returned from that instance of the function.The next nested instance of the function has a return statement, return(2*fact(1), and requires fact(1) return a value before it can evaluate the expression and return that value ....

    So this sequence unfolded is:

    Code (Text):

         i = fact(3)
             call fact(2)
                   call fact(1)
                       fact(1) returns a 1
                   fact(2) returns (2*1)
             fact3 returns(3*2)
         i = 6
     
     
  8. Feb 28, 2009 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    To the place where the function is called.

    If x is an expression of type int, then fact(x) is also an expression of type int. The value of fact(x) is the value that was returned.

    e.g., if the expression x has the value 7, then the value of fact(x) is the value of the expression 7 * fact(6).
     
  9. Feb 28, 2009 #8
    Okay.
    So fact (3) tries to return an int value. But since it is returning 3*(fact(2))
    fact (2) to has to be evaluated first.... and so on.
     
  10. Mar 1, 2009 #9
    I was under the impression that recursion carries serious performance penalties, so one should avoid it whenever possible even at the expense of code clarity. Perhaps outside of scientific computing this would be less of an issue, and I'm fairly sure that if you're using something like Lisp, recursive functions are perfectly acceptable.
     
  11. Mar 1, 2009 #10
    "I'm fairly sure that if you're using something like Lisp, recursive functions are perfectly acceptable."

    I would hope so.

    Recursion is perfectly fine, and don't let anybody tell you differently. Yes, it isn't as efficient as looping. This is, of course, an immediate consequence of the underlying hardware's implementation. It needn't have been such, and may not always be.

    Next, it is always possible to make a recursive function iterative, and vice versa. You never "need" to use recursion.

    You really should know how both recursion and iteration work.
     
  12. Mar 1, 2009 #11

    rcgldr

    User Avatar
    Homework Helper

    It comsumes stack space, but with GB's of memory and a large stack size specified, it shouldn't be an issue.
     
  13. Mar 1, 2009 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For quick functions, I believe the main problem with recursion is that it can't be inlined -- the computer spends more time doing the setup/cleanup for function calls than it does actually performing the calculation, and there is no opportunity for reusing registers or extracting constant subexpressions. There might even be an additional penalty when it gets the branch prediction wrong on the final iteration.

    Of course, a good compiler will automatically convert some forms of recursion into loops. :smile:
     
  14. Mar 1, 2009 #13
    Depends what's important to you..

    - performance
    - readability
     
  15. Mar 1, 2009 #14
    Alright, fine.

    Implemented both in C++.
    Running each 100,000,000 times for integers 0-9. Integer function.
    Timing them, in seconds.

    Iterative solution:
    45 seconds.

    Recursive solution:
    168 seconds.

    I'm actually sort of impressed by the difference. Here's the code I used:


    int factorial_it(int n)
    {
    int result = 1;

    for(int i = 2; i <= n; i++)
    result *= i;

    return result;
    }

    int factorial_rc(int n)
    {
    return (n <= 1 ? 1 : n * factorial_rc(n-1));
    }

    int main()
    {

    int t1, t2;

    t1 = (int)time(NULL);
    for(int n = 0; n < 100000000; n++)
    {
    for(int i = 0; i < 10; i++)
    {
    //int tmp = factorial_it(i);
    int tmp = factorial_rc(i);
    }
    }
    t2 = (int)time(NULL);

    cout << "Elapsed time: " << t2-t1 << endl;


    return 0;
    }
     
  16. Mar 1, 2009 #15

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What compiler / optimization settings? (/ architecture)

    I tried your code using MSVC++ 2008, both under DEBUG and RELEASE builds, and my results were:

    DEBUG: 50 and 158 (similar to what you got)
    RELEASE: 7 and 15


    I'm somewhat dissapointed that MSVC++ didn't turn the recursive function into a loop. Maybe compilers don't do that optimization, despite what I had learned?
     
  17. Mar 1, 2009 #16
    Well, strictly speaking, the way I wrote the factorial_rc function, it's not tail recursive. That's sort of the point... I believe you'll agree the multiplication, not the recursive call, is the "last" operation being done. I don't think compilers are written to do this optimization since, well, where would you stop it?

    I used the V.S. c++ thing at some sort of dingy lab I happened to be at when I did it. I didn't specify any compiler settings, and I was running under debug (almost certainly). As you can probably tell, I wasn't being too careful about it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: C++ Programmer Defined Factorial Function
Loading...