• Advertisement
Sign in to follow this  

Recursion in games

This topic is 4508 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

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

Share this post


Link to post
Share on other sites
Advertisement
Sure. Pretty much any tree structure will use recursion. In games that means ownership structures, pathfinding, certain LOS calculations, AI use...

Share this post


Link to post
Share on other sites
Recursion is often the most efficient (or one of the most efficient) algorithms for any given problem.

Though, as you use it, the term is sort of ambiguous. Do you mean recursive algorithms, or recursive data structures? Of course they both basically follow the same concept, but it would definately help me understand your comment "seems kinda pointless and a complete waste of memory+cpu power".

An example of a recursive algorithm is merge sort. Many simple algorithms can also be rewritten to use recursion (though, in this case, it would probably be out of preference).

Share this post


Link to post
Share on other sites
Quote:
Original post by TommySauder
referring to algorithms


The main use for recursion is to break very complex problems down into small, easily solved problems. When all the small problems are solved, then the large one is as well.

It's definately difficult to wrap your head around it at first though. [smile]

Recursion is the result of a popular method for designing algorithms called Divide-Conquer-Combine. Taken directly from my CS textbook:

Divide the problem into a number of subproblems.
Conquer the subproblems by solving them recursively. If the subproblems sizes are small enough, however, just solve the subproblems in a straightforward manner.
Combine the solutions to the subproblems into the solution for the original problem.

Another (though admittedly quite superficial) advantage to recursive algorithms is they generally require less code.

Share this post


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

Share this post


Link to post
Share on other sites
I understand how it works... All it does is runs infinite amount of functions until they all end up as true.

I guess I'll just have to read up on advanced uses on them to see the importance...

Share this post


Link to post
Share on other sites
Quote:
Original post by TommySauder
I understand how it works... All it does is runs infinite amount of functions until they all end up as true.

I guess I'll just have to read up on advanced uses on them to see the importance...


It doesn't do an "infinite" amount of iterations.

Usually, the number of iterations is a function of the input. An extremely well-designed algorithm will avoid dependency on input size. However, for complex problems, this is nearly impossible to do.

The proportionality between the number of iterations and the input size is typically expressed via asymptotic notation.

To given an example of a recursive algorithm:


// this function adds integers a and b with the restriction that it
// must do it 1 increment at a time, and do it recursively
int add(int a, int b)
{

// adding b to a is equivalent to add 1 to a b times

// the key in designing a recursive algorithm is to determine
// the point at which to stop making recursive calls.

// here, we know if b == 1, we can just explicitly do a + 1
if (b == 1)
return a + 1;
else {

// if we don't have the stop condition, we want to do
// something which will put us closer to having it.

// here I will use the identity

// a + b = (a + 1) + (b - 1)

// therefore,
return add(a + 1, b - 1);

// it's going to keep making calls until b == 1
// in which case, a will happen to equal a + b - 1.

// it then adds the last 1, and returns it.
}
}

Share this post


Link to post
Share on other sites
To give another such example, here is the "textbook" example of recursion.

You need to calculate the factorial of n, written n!, which is equal to 1 * 2 * 3 * ... * n-1 * n.

You can easily demonstrate that the factorial of any n is equal to the factorial of n-1 multiplied by n [(n-1)! * n], when n > 1. It is also important to note that 1! = 1. Using this information, you can write a program to calculate the factorial such as this one





int iterativeFactorial(int n) {
int result=1;

for (int i=1; i<=n; i++) {
result = result*i;
}

return result;
}

int recursiveFactorial(int n) {
if (n>1) { return n*factorial(n-1) }
else { return 1; }
}

int main() {
std::cout << "The factorial of ten is " << recursiveFactorial(10) << " (recursive).;
std::cout << "The factorial of ten is " << iterativeFactorial(10) << " (iterative).;
return 0;
}






In that particular case, we call factorial(10), which calls factorial(9), which calls factorial (8) ... you get the gist of it. Once the last call is resolved, the solution will be "propagated" up the call stack and will give the desired answer. You can also witness the elegance of the recursive solution compared to the iterative one. Factorials might not be the BEST way to use recursion, but it is a good way to illustrate it.

Edit: I'm damn tired and don't have access to a compiler. Should work tough.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster



You dont have to call a subroutine recursively to impliment 'recursion'.

Depending on the language's (and the compiler's) call/return efficiency it can be more efficient to do the recursive algorithm without recursive subroutine calls.

The code might not be as elegant and may make use of the 'evil' goto statement.

You also have to know the maximum depth because any local 'level' variables will reside on an array.

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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


Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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++?

Share this post


Link to post
Share on other sites
There was a pretty good article about it in the February 2004 issue of the C/C++ Users Journal.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
anyone can suggest a game which uses the method divide and conquer...!!??? anyone...?????!!!

Share this post


Link to post
Share on other sites
Quote:
Original post by k0ns0l3
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.


Hmm...
Without memoization or dynamic programming, a trivial recursive implementation for this would be overly complex (runtime). It may take ages to compute it for 1000 or even 100 since recursion will force recalculation of the same values over and over.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
anyone can suggest a game which uses the method divide and conquer...!!??? anyone...?????!!!


Well, let's see. Quicksort and mergesort are both divide-and-conquer algorithms. So, I guess that any game that ever needs to do any sorting anywhere in the code ends up using divide-and-conquer.

Share this post


Link to post
Share on other sites
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.
In some respects you're partly right.
Recursion is unnecessary when it is present in the form of tail-recursion (e.g. factorial), and can in fact worsen performance (though modern compilers will level it out with optimisations on). It often looks simpler (less lines of code) when written recursively though.
Then there are other recursive functions, that call themselves more than once. For functions like this there isn't really any better alternative. Usually some of the recursion can be eliminated, but not all. There are even sorting algorithms that call themselves 3 times recursively! (e.g. ProportionExtendSort)
As sorting is a basic concept used in all areas of programming, so is recursion.

But there are a lot more things that recursion is used for too.
What things do you know of that recursion can be used for?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement