Public Group

# first recursion function

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

## 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 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 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 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 on other sites
Quote:
 Original post by stormrunnerah, 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 on other sites
Quote:
 Original post by mozieAnd 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.

1. 1
2. 2
3. 3
4. 4
Rutin
11
5. 5

• 12
• 19
• 10
• 14
• 10
• ### Forum Statistics

• Total Topics
632665
• Total Posts
3007724
• ### Who's Online (See full list)

There are no registered users currently online

×