Sign in to follow this  

first recursion function

This topic is 4761 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

This topic is 4761 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this