Thread: recursion...recursion...

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    153

    recursion...recursion...

    howdy everyone,
    I was curious...or rather, I was having trouble trying to make a recursive function that returns the factorial of a user-defined number (if user enters n, then facorial of n (written n!)= n * (n -1)!...I'm not looking for the code for it...I'm just looking for a practical way to think about how to set up the flow of the recursion...any ideas? Thanks yet again for the unyielding help to my neverending pool of questions -Chap

  2. #2
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    1. Establish a base case. We know 0! = 1! = 1, so either of these would be the base case.
    2. Make sure the test for the base case is always evaluated.*
    3. Let f(n) be your function. You know how to define f(n+1) in terms of f(n), so just return the proper expression. Once it gets to the base case, it'll no longer go through recursion, but return an independent value.

    * And, obviously, make sure the input is valid. E.g. no negative integers.

    Hope this helps you think. Let me know if it is unclear/not what you want.

  3. #3
    Registered User
    Join Date
    Sep 2004
    Posts
    153
    hmmm...my brain is just not having any luck with recursion...I'm unclear as to a few things, maybe you can help...I was going to set up an array of n elements, is that going in the wrong direction? Zach, your reply helped, don't get me wrong...I just am having a hard time with recursion...can't mentally picture it which makes it difficult...any extra help would be great...thanks a lot for the help already -Chap

  4. #4
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Hmm... An array is certainly the wrong way to go. Perhaps a little illustration will help:
    Code:
    f(n)
       return g(f(n-1)); // Where g does some operation (add, multiply, take the square root and add 2, etc
    
    f(n-1)
       return g(f(n-2)); // Same deal
    
    ...
    
    f(r) // r is base case
       return k; // Where k does not depend on f(t) for any t (i.e. no more recursion).
    Note that f(n) and f(n-1) did exactly the same thing, with their particular input values being the only changing factor. No array was needed.

    I'd give an example, but it is hard to give one that doesn't immediately give away the solution to the factorial problem.

    Think in terms of the function stack: f(n) has not returned until f(n-1) returns, until f(r) returns for the base case, r. So, you know that 1! = 1, and you know the basic formula for factorials. Now what is the 'g' function from the above pseudo-code?
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  5. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Code:
    double Factorial(double cur_num)
    {
      static double rvalue=0.0;
     
      if (cur_num)<=0 return (rvalue);
     
      if (rvalue==0.0) 
      {
    	rvalue=1.0; 
    	rvalue*=cur_num;
      } else rvalue*=cur_num;
     
      Factorial(cur_num-1.0);
    }
    I think this should work.

    I couldn't think of any way to explain this w/o giving it away.

    Here is another example of recursion.

    Code:
    void QuadExample(int depth,int left,int top,int right,int bottom)
    {
      if (depth<=0 || ((right-left)<=2)) return;
     
      int midx=(left+right)/2;
      int midy=(top+bottom)/2;
     
      //Draw randomly colored square
      RGB color(rand()% 255,rand ()%255, rand%255);
      DrawSquare(left,top,right,bottom,color);
     
      QuadExample(depth-1,left,midx,top,midy);
      QuadExample(depth-1,midx,top,right,midy);
      QuadExample(depth-1,left,midy,midx,bottom);
      QuadExample(depth-1,midx,midy,right,bottom);
    }
    This only works if left and top both start at 0. I didn't want to add code to confuse the matter in order to fix this. Also right and bottom are assumed to be larger values than left and top.
    Last edited by VirtualAce; 10-04-2004 at 08:58 PM.

  6. #6
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Be careful that the value at non-integral inputs will be bogus values in that solution. It will approximate larger values than if you used an integral type, though.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  7. #7
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Which is why I used double. It is not wise to check exact equality with doubles, but I figured the values involved were never going to get large enough for it to matter much.

    If you don't like the doubles then use unsigned long integers, but that does limit your max range to the max value of a 32-bit unsigned value. Keep in mind with factorial functions it is very easy to overflow your data type.

  8. #8
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Certainly. And it is a fair bit more clever than most factorial implementations, too. I don't disagree with you.

    My only real qualm about it is that you have to decide what to do with non-integral inputs (if it is within some distance from an integer, round perhaps, and return 0 or throw an exception otherwise?). I'm not sure what the best solution for that is.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  9. #9
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Well if you wanted an integral based factorial then you would simply round up to or down to the nearest integer. You would keep the double data type but use it as an integral value. In fact in some cases this might be faster since FPUs are extremely fast. But on an Intel x86 IA32/64 processor all integer operations execute at half a clock tick. Yep....half a cycle. That's hard to beat.

    The only other solution is to create/use a large integer class. Similar to the way 32-bit values were added way back when only 16 bit registers were available. Randall Hyde's AOA has a fair amount of information on how this is done. Essentially the number limitations then are...well...limitless unless your number somehow fills all of available RAM, which we hope it doesn't.

    It is possible with my function that you will get a stack overflow with very large values - but I do mean extremely large values. This is another drawback to it.

    There is also a way to store 64-bit values on IA32 by cleverly using MMX registers. Consult the Intel MMX manual for more info.

  10. #10
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    I'm not arguing about using doubles... I think that's a good idea. I'm just saying that there needs to be some mechanism to deal with non-integral inputs well... Perhaps throwing an exception or something of that nature if the number is too far away from an integral value instead of returning a somewhat unexpected result.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  11. #11
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Factorial are ONLY for integer. Never floating point number...
    Chaplin, this is recursion:
    7!=7*6!
    6!=6*5!->7!=7*6*5!
    5!=5*4!->6!=6*5*4!->7!=7*6*5*4!

    Understand (not the factorial, the algorithm)??

  12. #12
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Quote Originally Posted by Zach L.
    I'm just saying that there needs to be some mechanism to deal with non-integral inputs well
    Of course there is:
    Code:
    int factorial(int n);
    ...
    factorial(8.56);//8.56 is rounded to integer 8-> better handling than this??

  13. #13
    Registered User
    Join Date
    Oct 2004
    Posts
    26
    Just FYI on evaluating the factorial of nonintegral arguments: the factorial function is just a special case of the gamma function, which is studied in courses on complex analysis. The definition is n! = gamma(n+1), where

    gamma(z) = integral_{from 0 to +infinity} t^{z-1}e^{-t}dt

    You can find code to evaluate the gamma function for positive real z from the book numerical recipes in C (requires acrobat reader)

    So, in fact,

    8.0! = gamma(9.0) = 40320
    8.1! = gamma(9.1) = 49973.70894963751198...
    8.2! = gamma(9.2) = 62010.76389578186354...
    8.3! = gamma(9.3) = 77035.5579637191695.....


    chaplin--in your other post on recursion earlier, I gave a pretty detailed explanation of how to structure recursive functions, and explicitly used the factorial as an example. Look at that post again!
    Last edited by zzzaaahhh; 10-05-2004 at 04:54 PM.

  14. #14
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Yeah, the gamma function is defined everywhere except negative integral values, so .5!, etc makes sense (in fact, .5! = pi/2, I believe).

    Quote Originally Posted by xErath
    Of course there is:
    Code:
    int factorial(int n);
    ...
    factorial(8.56);//8.56 is rounded to integer 8-> better handling than this??
    It really depends on what the user expects. What do you think someone expected to get out of the factorial when they put in 8.56!? Was it 8!, 9!, or should it spit out an error because it doesn't know what you're talking about
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  15. #15
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Someone that writes factorial(8.56) doesn't know what a factorial is... Let them use the gamma function.
    Again: factorial IS ONLY for positive integers, a particular case of the gamma funtion.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM