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

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.

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

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?

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.

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.

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.

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.

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.

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.

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)??

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??

---

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!

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

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.

It all depends on how you define factorial. all definitions I've seen have been something like this:
0! = 1
n! = n*(n-1)!
n is integet >= 0

You could of course define factorial with the gamma function, but since factorial is used mostly in combinatorics it wouldn't make sense.