Recursion in games

For Beginners

Started by TommySauder September 02, 2005 07:59 PM

35 comments, last by Sandman 18 years, 7 months ago

745

September 02, 2005 11:59 PM

Quote:Original post by TommySauder
Just wondering if there's an actual use to recursion in games... seems kinda pointless and a complete waste of memory+cpu power.

For the most part, you can change an iterative loop into a recursive loop and vice versa. The only difference will be that the recursive version will pile up on the stack. However, there's more to the story than just that:

1) Some algorithms are much clearer in one form than the other. If you can spare the "memory+cpu", then use the clearer one.

2) If you compiler can perform tail-call optimizations, there will be no difference in "memory+cpu" (it essentially turns a recursive algorithm into its iterative version). Thus, you can feel free to choose the clearer form with no performance worries.

3) Unfortunately, I don't think many C/C++ compilers do this optimization (I think GCC will do it?). On the other hand, C/C++ aren't the only languages out there.

Binomine

611

September 03, 2005 12:05 AM

Quote:Original post by TommySauder
I guess I'll just have to read up on advanced uses on them to see the importance...

Now for at least one 'importance'(at least in game development), we'll use the factorial example. Every recursive function can be rewritten as a iterative function, as xMcBaiNx has prefectly shown.

Now, if you go through the recursive factorial example, you get an OS stack.

-------------
| Nth_CALL |
-------------
| ..._CALL |
-------------
| 2nt_CALL |
-------------
| 1st_CALL |
------------

While in the iterative function, instead of an OS stack, you repeat the same code.

Now imagine that instead of simply repeating the same code, you need to store a value after each loop and remember it for later. For the iterative method, we would need a stack to store and retreave the info. The recursive method already gives us a stack, written by the OS, which should be much faster than our iterative stacks, because it exists in OS space instead of user space.

That is the performance gain by using recursion.

hplus0603

11,916

September 03, 2005 12:19 AM

I believe the most commonly used recursive algorithm in games programming is the various spatial hierarchy traversers. Something like:

void DrawAll( Tree * top, Bounds * bounds, bool allInside ) {  for( Tree * child = top->firstChild(); child; child = top->nextChild(child) ) {    bool inside = allInside;    bool childAllInside = allInside;    if( !allInside ) {      bounds->checkNode( child, &inside, &childAllInside );    }    if( inside ) {      DrawAll( child, bounds, childAllInside );    }  }  top->Draw();}

Whether it's octrees, kd-trees, BSP trees, ... doesn't really matter; they all use this traversal algorithm (but the specifics of "checkNode()" and "nextChild()" vary).

enum Bool { True, False, FileNotFound };

Roboguy

794

September 03, 2005 12:57 AM

Quote:Original post by Way Walker
Quote:Original post by TommySauder
Just wondering if there's an actual use to recursion in games... seems kinda pointless and a complete waste of memory+cpu power.

2) If you compiler can perform tail-call optimizations, there will be no difference in "memory+cpu" (it essentially turns a recursive algorithm into its iterative version). Thus, you can feel free to choose the clearer form with no performance worries.

That can only be done in some cases (when the last operation in the function is the recursive call, IIRC).

http://www.roboguy.net(WIP) - lisperati - SICP - Haskell - Python - OCaml - Lambda the Ultimate - Good Math, Bad Math - Wiki (not Wikipedia) - Pure - Term-Rewriting Functional Language

Spoonbender

1,258

September 03, 2005 04:30 AM

Quote:Original post by Way Walker
3) Unfortunately, I don't think many C/C++ compilers do this optimization (I think GCC will do it?). On the other hand, C/C++ aren't the only languages out there.

I'm pretty sure most compilers can do it. But as was said, it can only be done in some cases.

TommySauder

186

Author

September 03, 2005 07:27 AM

Quote:void DrawAll( Tree * top, Bounds * bounds, bool allInside ) {
for( Tree * child = top->firstChild(); child; child = top->nextChild(child) ) {
bool inside = allInside;
bool childAllInside = allInside;
if( !allInside ) {
bounds->checkNode( child, &inside, &childAllInside );
}
if( inside ) {
DrawAll( child, bounds, childAllInside );
}
}
top->Draw();
}

what exactly does that do?

SiCrane

11,840

September 03, 2005 07:29 AM

Quote:Original post by Spoonbender
Quote:Original post by Way Walker
3) Unfortunately, I don't think many C/C++ compilers do this optimization (I think GCC will do it?). On the other hand, C/C++ aren't the only languages out there.

I'm pretty sure most compilers can do it. But as was said, it can only be done in some cases.

No, tail recursion in C/C++ is a very difficult topic. Most C/C++ compilers don't implement tail recursion, and even for those that do, it's fairly easy to create a function that looks it will be optimized but won't be.

k0ns0l3

118

September 03, 2005 07:42 AM

Quote:Original post by vaneger
Well as an example try writing a function to print the fibinocci sequence ( or rather the first X numbers of the sequence) make one without recursion and one with recursion and you should see some difference in quality of the code. FYI the fib sequence starts with 1 and the next number is equal to the sum of the two previous numbers so it starts as : 1 (0+1), 1 (1+1), 2 (2+1), 3 (2+3), 5 (5+3), 8 .... etc.

as others have stated recursive code is fundemental to some algorithms and is the best way to code them.

Anonymous

September 03, 2005 02:16 PM

Quote:Original post by Roboguy
Quote:Original post by Way Walker
Quote:Original post by TommySauder
Just wondering if there's an actual use to recursion in games... seems kinda pointless and a complete waste of memory+cpu power.

2) If you compiler can perform tail-call optimizations, there will be no difference in "memory+cpu" (it essentially turns a recursive algorithm into its iterative version). Thus, you can feel free to choose the clearer form with no performance worries.

That can only be done in some cases (when the last operation in the function is the recursive call, IIRC).

i.e. "tail-call" recursion.

Quote:Original post by SiCrane
No, tail recursion in C/C++ is a very difficult topic. Most C/C++ compilers don't implement tail recursion, and even for those that do, it's fairly easy to create a function that looks it will be optimized but won't be.

Could you explain or point me to a resource that explains the difficulties in C/C++?

Way Walker

745

September 03, 2005 02:18 PM

[imwithstupid] AP was me.

Recursion in games

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Recursion in games

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines