Server Help Forum Index Server Help
Community forums for Subgame, ASSS, and bots
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   StatisticsStatistics   RegisterRegister 
 ProfileProfile   Login to check your private messagesLogin to check your private messages   LoginLogin (SSL) 

Server Help | ASSS Wiki (0) | Shanky.com
"Recursive" functions

 
Post new topic   Reply to topic Printable version
 View previous topic  forums Post :: Post Hahahaha! Nice new forum name!  View next topic  
Author Message
Solo Ace
Yeah, I'm in touch with reality...we correspond from time to time.


Age:37
Gender:Gender:Male
Joined: Feb 06 2004
Posts: 2583
Location: The Netherlands
Offline

PostPosted: Thu Jul 15, 2004 1:59 am   Post maybe stupid    Post subject: "Recursive" functions Reply to topic Reply with quote

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 icon_wink.gif).

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?
Back to top
View users profile Send private message Add User to Ignore List
CypherJF
I gargle nitroglycerin


Gender:Gender:Male
Joined: Aug 14 2003
Posts: 2582
Location: USA
Offline

PostPosted: Thu Jul 15, 2004 3:20 am   Post maybe stupid    Post subject: Reply to topic Reply with quote

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

But that there is a recursive function.
_________________
Performance is often the art of cheating carefully. - James Gosling
Back to top
View users profile Send private message Add User to Ignore List
Mine GO BOOM
Hunch Hunch
What What
Hunch Hunch<br>What What


Age:41
Gender:Gender:Male
Joined: Aug 01 2002
Posts: 3615
Location: Las Vegas
Offline

PostPosted: Thu Jul 15, 2004 3:26 am   Post maybe stupid    Post subject: Reply to topic Reply with quote

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;
}
Back to top
View users profile Send private message Add User to Ignore List Send email
Mr Ekted
Movie Geek


Gender:Gender:Male
Joined: Feb 09 2004
Posts: 1379
Offline

PostPosted: Thu Jul 15, 2004 3:32 am   Post maybe stupid    Post subject: Reply to topic Reply with quote

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.
_________________
4,691 irradiated haggis!
Back to top
View users profile Send private message Add User to Ignore List
Bak
?ls -s
0 in


Age:26
Gender:Gender:Male
Joined: Jun 11 2004
Posts: 1826
Location: USA
Offline

PostPosted: Thu Jul 15, 2004 10:34 am   Post maybe stupid    Post subject: Reply to topic Reply with quote

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.


Last edited by Bak on Thu Jul 15, 2004 7:56 pm, edited 2 times in total
Back to top
View users profile Send private message Add User to Ignore List AIM Address
Dr Brain
Flip-flopping like a wind surfer


Age:39
Gender:Gender:Male
Joined: Dec 01 2002
Posts: 3502
Location: Hyperspace
Offline

PostPosted: Thu Jul 15, 2004 10:56 am   Post maybe stupid    Post subject: Reply to topic Reply with quote

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.
_________________
Hyperspace Owner

Smong> so long as 99% deaths feel lame it will always be hyperspace to me
Back to top
View users profile Send private message Add User to Ignore List AIM Address Yahoo Messenger MSN Messenger
Mine GO BOOM
Hunch Hunch
What What
Hunch Hunch<br>What What


Age:41
Gender:Gender:Male
Joined: Aug 01 2002
Posts: 3615
Location: Las Vegas
Offline

PostPosted: Thu Jul 15, 2004 1:49 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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.
Back to top
View users profile Send private message Add User to Ignore List Send email
Mr Ekted
Movie Geek


Gender:Gender:Male
Joined: Feb 09 2004
Posts: 1379
Offline

PostPosted: Thu Jul 15, 2004 1:51 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

Wow, we all sort of agree on this subject. Lock this thread before Qndre posts something!
Back to top
View users profile Send private message Add User to Ignore List
Qn... err Anonymous
Guest


Offline

PostPosted: Thu Jul 15, 2004 3:12 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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.
Back to top
Mr Ekted
Movie Geek


Gender:Gender:Male
Joined: Feb 09 2004
Posts: 1379
Offline

PostPosted: Thu Jul 15, 2004 3:16 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

rofl
Back to top
View users profile Send private message Add User to Ignore List
Dr Brain
Flip-flopping like a wind surfer


Age:39
Gender:Gender:Male
Joined: Dec 01 2002
Posts: 3502
Location: Hyperspace
Offline

PostPosted: Thu Jul 15, 2004 4:01 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

^.^

Very nicely done.
Back to top
View users profile Send private message Add User to Ignore List AIM Address Yahoo Messenger MSN Messenger
-Smong-
Guest


Offline

PostPosted: Thu Jul 15, 2004 5:56 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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.
Back to top
Mine GO BOOM
Hunch Hunch
What What
Hunch Hunch<br>What What


Age:41
Gender:Gender:Male
Joined: Aug 01 2002
Posts: 3615
Location: Las Vegas
Offline

PostPosted: Thu Jul 15, 2004 7:31 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

-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
Back to top
View users profile Send private message Add User to Ignore List Send email
Bak
?ls -s
0 in


Age:26
Gender:Gender:Male
Joined: Jun 11 2004
Posts: 1826
Location: USA
Offline

PostPosted: Thu Jul 15, 2004 7:34 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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.
Back to top
View users profile Send private message Add User to Ignore List AIM Address
Dr Brain
Flip-flopping like a wind surfer


Age:39
Gender:Gender:Male
Joined: Dec 01 2002
Posts: 3502
Location: Hyperspace
Offline

PostPosted: Thu Jul 15, 2004 10:28 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

Also populations of bee hives will reflect fibonacci numbers for each generation (under ideal conditions, of course).
Back to top
View users profile Send private message Add User to Ignore List AIM Address Yahoo Messenger MSN Messenger
Solo Ace
Yeah, I'm in touch with reality...we correspond from time to time.


Age:37
Gender:Gender:Male
Joined: Feb 06 2004
Posts: 2583
Location: The Netherlands
Offline

PostPosted: Fri Jul 16, 2004 1:26 am   Post maybe stupid    Post subject: Reply to topic Reply with quote

Hmm'k, thanks for replying all.
His reply to you: "it's not a serious app! write the damn loop for me then!", hehe. icon_wink.gif
Back to top
View users profile Send private message Add User to Ignore List
50% Packetloss
Server Help Squatter


Age:40
Gender:Gender:Male
Joined: Sep 09 2003
Posts: 561
Location: Santa Clarita, California
Offline

PostPosted: Fri Jul 16, 2004 2:24 am   Post maybe stupid    Post subject: Reply to topic Reply with quote

same with the # of leaves on plants and hundreds of other things
Back to top
View users profile Send private message Add User to Ignore List Send email AIM Address
Bak
?ls -s
0 in


Age:26
Gender:Gender:Male
Joined: Jun 11 2004
Posts: 1826
Location: USA
Offline

PostPosted: Fri Jul 16, 2004 11:53 am   Post maybe stupid    Post subject: Reply to topic Reply with quote

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.
Back to top
View users profile Send private message Add User to Ignore List AIM Address
D1st0rt
Miss Directed Wannabe


Age:37
Gender:Gender:Male
Joined: Aug 31 2003
Posts: 2247
Location: Blacksburg, VA
Offline

PostPosted: Fri Jul 16, 2004 1:45 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

This is probably one of the only uses of recursive functions
_________________

Back to top
View users profile Send private message Add User to Ignore List Visit posters website
Display posts from previous:   
Post new topic   Reply to topic    Server Help Forum Index -> Trash Talk All times are GMT - 5 Hours
Page 1 of 1

 
Jump to:  
You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
View online users | View Statistics | View Ignored List


Software by php BB © php BB Group
Server Load: 35 page(s) served in previous 5 minutes.

phpBB Created this page in 0.659106 seconds : 43 queries executed (80.8%): GZIP compression disabled