Server Help :: View topic - "Recursive" functions

Server Help

Trash Talk - "Recursive" functions

Solo Ace - Thu Jul 15, 2004 1:59 am
Post subject: "Recursive" functions

Today someone showed me the source of a program he wrote, and he used "recursive" function calls (not sure if that's the right name

).

What he used looks like this (simplified, of course):

Code: Show/Hide

int main (int argc, char *argv[])
{
function(0, 20);
return 0;
}

void function(int moo, int blah)
{
if (moo == blah)
// Do something here :P
else
function(moo + 1, blah);
}

I think this is ugly, but I'm wondering, is this as bad as it looks like? Should he find a better way?

CypherJF - Thu Jul 15, 2004 3:20 am
Post subject:

Recursive methods/functions are good in some ways, and bad in others.

But that there is a recursive function.

Mine GO BOOM - Thu Jul 15, 2004 3:26 am
Post subject:

Good example for recursive functions would be factorials. Quick examples:

Code: Show/Hide

int fact (int num) {
if (num > 1)
return fact(num - 1) * num;
return 1;
}

Or you could just make it into a loop, which will run a lot faster, and save more memory.

Code: Show/Hide

int fact (int num) {
int val = 1;
for ( ; num > 1; num--)
val *= num;
return val;
}

Mr Ekted - Thu Jul 15, 2004 3:32 am
Post subject:

Recursiveness is a good way to explain/model certain things. but hardly ever a good way to implement them. As with the example above, use loops whenever possible, even if it's tougher to code.

Bak - Thu Jul 15, 2004 10:34 am
Post subject:

all recursive functions can be rewritten "iteratively" (not recursively) using a stack. And it'll probably save memory.

It is a lot easier to write recursive functions for things like trees or linked lists, once you know how to write them. You just have to be careful you're not doing the same calculations over and over again... like the fibinacii numbers example:

Code: Show/Hide

int fib(int num)
{
if (num > 2)
{
return fib(num - 1) + fib(num - 2);
}

return 1;
}

This is a terrible use of recursion... as every call results in 2 more... which result in 2 more... once you call the function with num around 50-60, the result takes FOREVER.

The idea when writing recursive functions if you have 2 cases... a base case and a recursive case. The base case is the simplest case possible where the answer is known (for the fib example it's when rv <= 1. Then there's a recursive case which has to somehow make the problem approach the base case(in the fib example if the return fib(num - 1) + fib(num - 2); ). If the problem doesn't get simpler you have an infinate loop, although the program might quit because of too many function calls inside one another, maybe just on debug mode. just imagine what would happen if instead of return fib(num - 1) + fib(num - 2); it was just return fib(num);

Here's an example where recursion does help make the code simpler, deleteing the nodes of a binary tree:

Code: Show/Hide

void deleteTreeNode(Node *node)
{
if (node)
{
   deleteTreeNode(node->left);
   deleteTreeNode(node->right);

   delete node;
   //node = 0; if we passed the pointer by reference
}
}

All you have to do to delete a tree, or any section of the tree is call this function with the root of your tree/subtree.

now the base case is where node == 0, or NULL. If this is the case do nothing. The recursive case is where node != 0, in which case we delete the children, and then the node itself.

Dr Brain - Thu Jul 15, 2004 10:56 am
Post subject:

Recursive functions can overload the stack after too many recursions.

The only case I've ever used a function calling itself for is when some initial conditions aren't met, and then it sets them and calls itself again. Those initial conditions involve database queries, so it's easier to understand (and more efficient) just calling the query over again. Because the function is only ever called once more, it might not technicly be a recursive call.

Any other REAL programming task (not mathematics) can be probably be done better with a loop.

Mine GO BOOM - Thu Jul 15, 2004 1:49 pm
Post subject:

Dr Brain wrote:

The only case I've ever used a function calling itself for is when some initial conditions aren't met, and then it sets them and calls itself again. Those initial conditions involve database queries, so it's easier to understand (and more efficient) just calling the query over again. Because the function is only ever called once more, it might not technicly be a recursive call.

This is actually one of the few times where it would probably be better to use a goto.

Mr Ekted - Thu Jul 15, 2004 1:51 pm
Post subject:

Wow, we all sort of agree on this subject. Lock this thread before Qndre posts something!

Anonymous - Thu Jul 15, 2004 3:12 pm
Post subject:

OMG LOL they're trying to trick you solo ace don't believe them! Recursive functions not only are easy to do and understand they speed everything up! I've confirmed it myself!

I use them in all of my ASM and javascript programs, here's an example that finds the length of an array of characters(stored as ints):

Code: Show/Hide

private static constant inline void&* what'slength(int[] this, int length) const;
{
start:
if (this.currentcharacter == NULL;
goto loop:

loop:
   for(this.currentcharacter = 0;this < length;++this.currentcharacter){
      boolean counter = 0;

      counter = 1 + what'slength(this + 1,length - 1);

      if (length = 0);
         return 0;
      if (lenfth = 1)
         return 1;
      if (length == -1)
         return NULL;
      if length < -1);
         return false;
   };

if (this.currentcharacter = NULL);
   goto start;

if (what'slength(this,length){
   goto start;
start:
   return this + length;
}
else if (what'slength(this,length + 1) < -5){
#define goto goto loop:

   switch(length){
   case NULL:
      return;
   }

   goto;
}

while (this) { #define ensurevalid
endsurevalid(this[x]; ++this++;}

return length;

);

I know it looks intimidating but it's inline that means it runs faster than any loop you could make. I'm so good at java LOL. The compiler might give you a warning but you can ignore it, it's worth the speed increase.

Mr Ekted - Thu Jul 15, 2004 3:16 pm
Post subject:

rofl

Dr Brain - Thu Jul 15, 2004 4:01 pm
Post subject:

^.^

Very nicely done.

Anonymous - Thu Jul 15, 2004 5:56 pm
Post subject:

It looks to me like the factoral returns 1 or 0. I've no idea about the fibonacci one, I guess if you need those functions you know all the mathematical stuff behind it. Also shows it's a good idea to comment your code.

Mine GO BOOM - Thu Jul 15, 2004 7:31 pm
Post subject:

-Smong- wrote:

It looks to me like the factoral returns 1 or 0.

Ever notice a function on calculators that are just a ! only? What it does is multiply every number upto the one you entered together.

So 5! would be 5 * 4 * 3 * 2 * 1. This takes a lot of calculations to do when you get to high numbers, as the numbers become large pretty fast, so saving a bit of time at each step helps.

Factorials are also a good way to test how fast your calculator is to another. Most max out with 69!, since most calculators only go upto 10^100 - 1.

For the hell of it, 69! = 171122452428141311372468338881272839092270544893520369393648040923257279754140647424000000000000000, or 1.71122452 × 10^98

Bak - Thu Jul 15, 2004 7:34 pm
Post subject:

Factorial is defined to be the product of all the numbers from one up to the number the factorial is of. So 1! (that's one factorial) will be 1.
2! = 1 * 2 = 2
3! = 1 *2 * 3 = 6
4! = 1 * 2 * 3 * 4 = 24

the fibinacii numbers are like this: the first two number in the sequence are 1 and 1. Every number after that is the sum of the previous two numbers. so the 3rd number will be the sum of the previous two... 1 + 1 = 2. The 4th number = 1 + 2 = 3. The pattern continues...

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

the significance is that lots of occurences in nature use numbers in this sequence, like the amount of petals on a flower will usually be one of these numbers.

Dr Brain - Thu Jul 15, 2004 10:28 pm
Post subject:

Also populations of bee hives will reflect fibonacci numbers for each generation (under ideal conditions, of course).

Solo Ace - Fri Jul 16, 2004 1:26 am
Post subject:

Hmm'k, thanks for replying all.
His reply to you: "it's not a serious app! write the damn loop for me then!", hehe.

50% Packetloss - Fri Jul 16, 2004 2:24 am
Post subject:

same with the # of leaves on plants and hundreds of other things

Bak - Fri Jul 16, 2004 11:53 am
Post subject:

yeah... you should use recursive functions if you 1. don't care about efficiency (bad programming) or 2. it's on a timed comp sci test and they only give you half a page to write on.

D1st0rt - Fri Jul 16, 2004 1:45 pm
Post subject:

This is probably one of the only uses of recursive functions