Jump to content
  • Advertisement
Sign in to follow this  
TommySauder

Recursion in games

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

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!