Back to For Beginners

first recursion function

For Beginners

Started by mozie December 01, 2004 04:29 PM

4 comments, last by Zahlman 19 years, 4 months ago

mozie

194

Author

December 01, 2004 04:29 PM

I am learning recursion, and at cprogramming.com tut 16 the end of the lesson they give you a problem to solve. Here is a copy so you dont need to click:

Quote: This is just the beginning of the usefulness of recursion. Heres a little challenge, use recursion to write a program that returns the factorial of any number greater than 0. (Factorial is number*number-1*number-2...*1).

So I wanted to know if the code I wrote will work, I'm at work right now so I dont get to run it throught the compiler, but I think I have that part right anyway :). The first one should be stright-to-the-point, the second one was for fun, I wanted to write the function w/o having to use a constant (ie, > 1, == 0, return 1). So the second was *should* do the same, I just wanted a little bit of a challenge. :) Please let me know what you think.


// calculates facoral
// my first recursave function.

int func_fact	(int tfact)
{
	if(tfact > 1) 
		return tfact * func_fact(tfact-1);
	else 
		return 1;
}

int func_factx	(int tfact)
{
	int afact = tfact;
	afact--;            // make afact one less than tfact
	if((afact + afact)) // if afact is not 0, keep solving
		return tfact * func_fact(afact);
	else		    // if afact is zero, then tfact is 1
		return tfact;
}

Thank you! EDIT: the func_factx does not check for tfact == 0 before afact--. in the case of func_factx(0) called, then afact= tfact (=0), so when afact--; (= -1), then the (afact + afact) will = -2, will this cause the if statement to take a -2 as FALSE?

JuNC

236

December 01, 2004 04:44 PM

If tfact is 0:

afact = 0
afact-- -> afact = -1

afact + afact = -1 + -1 = -2

-> takes first branch -> BLAM infinite recursion :)

EDIT: you edited while I was typing :)

-2 is true (any non-zero value is).

Note that even if that was the case, the code wouldn't return the right value for 0!

chi

122

December 01, 2004 04:48 PM

Well, both functions will work, but I don't see why you do

if((afact + afact))

when you can do the same with

if(afact)

tfact will never be 0 because when you call

return tfact * func_fact(afact);

afact is not zero. But, if function is called from somewhere else with <1 value, func_factx wuold never end because only zero is FALSE and all other values (including negative) are TRUE.

N/A

stormrunner

720

December 01, 2004 04:48 PM

ah, but the real question is, does your recursive factorial use template metaprogramming ?

template<int N>class Factorial {public:    enum { value = N * Factorial<N-1>::value };};class Factorial<1> {public:    enum { value = 1 };};int main(){  Factorial<5> io;  cout << io.value << endl;  return 0;}

seriously, though, you got a good start on recursion (both your functions work fine). just remember that as cool as recursion is, and it is handy in many situations, it can be a pain to debug. so use with care.
cheers.
<edit::

Quote:afact is not zero. But, if function is called from somewhere else with <1 value, func_factx wuold never end because only zero is FALSE and all other values (including negative) are TRUE.

actually, it just returns the negative value.

- stormrunner

mozie

194

Author

December 01, 2004 05:05 PM

Quote:Original post by stormrunner
ah, but the real question is, does your recursive factorial use template metaprogramming ?

I don't think it does, because I wouldnt know how to define to someone what using "template metaprogramming" really means yet. :)

Quote:
template<int N>class Factorial {public:    enum { value = N * Factorial<N-1>::value };};class Factorial<1> {public:    enum { value = 1 };};int main(){  Factorial<5> io;  cout << io.value << endl;  return 0;}
seriously, though, you got a good start on recursion (both your functions work fine). just remember that as cool as recursion is, and it is handy in many situations, it can be a pain to debug. so use with care.
cheers.
<edit::
Quote:afact is not zero. But, if function is called from somewhere else with <1 value, func_factx wuold never end because only zero is FALSE and all other values (including negative) are TRUE.

actually, it just returns the negative value.

So, it does not accuratly check for 0 then, right?

And if it does not, could changing the unput param to unsigned int, prevent a negitave number, if -1 (0xFFFFFFFF) was passed, it would be treated as 4,xxx,*that big 32 bit number*?

That way I could use the: if(afact) inplace of if(afact+afact) because it couldnt be a negitave number, I think :)

Zahlman

1,682

December 01, 2004 06:12 PM

Quote:Original post by mozie
And if it does not, could changing the unput param to unsigned int, prevent a negitave number, if -1 (0xFFFFFFFF) was passed, it would be treated as 4,xxx,*that big 32 bit number*?

Yep. On the other hand, you probably don't want to be trying to calculate the factorial of "that big 32 bit number". :)

Anyway, the factorial function is a classic example of something you can do recursively, but it's probably not the best example because doing it iteratively is pretty easy:

int factorial(int input) {  int f = 1;  for (int i = 1; i <= input; i++) { f *= i; }  return f; // will return 1 for negative input values}

There are, of course, plenty of problems out there that are a lot easier to do with recursion - for example, drawing various sorts of fractals. You can always translate these things into some non-recursive form, but generally you end up implementing "the stack" yourself, which is a bad idea.

Quote:That way I could use the: if(afact) inplace of if(afact+afact) because it couldnt be a negitave number, I think :)

You "can" use it anyway; "afact + afact" is the same as "afact * 2", and 2 * 0 == 0, and 2 * (something != 0) != 0.

first recursion function

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

first recursion function

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines