Recursivity Explanation in c++

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • Deanm007
    New Member
    • Apr 2010
    • 37

    #1

    Recursivity Explanation in c++

    Hi

    Say we enter 4 at the prompt, factorial function is called with 4 as the argument. Now 4*factorial(4-1). The function calls itself now. So what happens at this point?

    1.Does it return anything to main or does it call the function again from within?

    2. Where would it hold the 4, the 3, and the 2 to multiply it to get 24? In other words, what is the step by step procedure to get 24?

    Thanks a lot.


    Code:
    #include <iostream>
    using namespace std;
    
    long factorial (long x)
    {
      if (x > 1)
       return (x * factorial (x-1)); //calling the function from within the function.
      else
       return (1);
    }
    
    int main ()
    {
      long num;
      cout << "Enter a number: ";
      cin >> num;
      cout << num << "! = " << factorial (num);
      return 0;
    }
  • newb16
    Contributor
    • Jul 2008
    • 687

    #2
    1. It will return to main after everything is calculated.
    2. Most likely on the stack, where local variables and passed parameters are stored*. When it multiplies 2 by 1, there are three stack frames with local variables - for factorial called with argument equal 4,3, and 2.

    Yes, they can be also passed in registers.

    Comment

    • code green
      Recognized Expert Top Contributor
      • Mar 2007
      • 1726

      #3
      Logically it would use the mathematical BODMAS rule.
      So the command in the bracket would be implemented first.
      So factorial would be called again and again until !(x>1).

      Nothing could be returned to main until !(x>1).then the else is called.
      I don't believe this function works. Does it?

      It looks like it is missing a static

      Comment

      • Banfa
        Recognized Expert Expert
        • Feb 2006
        • 9067

        #4
        Looks like it should work to me, what makes you think it wont.

        Comment

        • Dheeraj Joshi
          Recognized Expert Top Contributor
          • Jul 2009
          • 1129

          #5
          It looks like it is missing a static
          You mean static keyword for the function?

          Regards
          Dheeraj Joshi

          Comment

          • code green
            Recognized Expert Top Contributor
            • Mar 2007
            • 1726

            #6
            It looks like the value of (x-1) is continually passed to factorial()
            without even the x * being implemented.

            I mean a static variable to hold the value of x.
            Or pass x as a pointer or reference.

            I am beginning to doubt myself. Am I missing something here?

            Comment

            • Dheeraj Joshi
              Recognized Expert Top Contributor
              • Jul 2009
              • 1129

              #7
              It compiles and run's properly. No need of static, for variable x i think.

              Regards
              Dheeraj Joshi

              Comment

              • code green
                Recognized Expert Top Contributor
                • Mar 2007
                • 1726

                #8
                Apologies. I am seeing brackets that are not even there.

                Comment

                • donbock
                  Recognized Expert Top Contributor
                  • Mar 2008
                  • 2427

                  #9
                  Use of static or global variables inside a recursive function is typically ill-advised.

                  Comment

                  • Deanm007
                    New Member
                    • Apr 2010
                    • 37

                    #10
                    Well, I just got here but it appears someone already chose newb16 as best answer for me. LOL. This is too funny. Anyway, it is the best answer. Thanks to everyone for chipping in.. By the way, it does compile and run.

                    Comment

                    Working...