Recursion in games
Author
Just wondering if there's an actual use to recursion in games... seems kinda pointless and a complete waste of memory+cpu power.
Sure. Pretty much any tree structure will use recursion. In games that means ownership structures, pathfinding, certain LOS calculations, AI use...
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).
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).
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.
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.
as others have stated recursive code is fundemental to some algorithms and is the best way to code them.
Author
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...
I guess I'll just have to read up on advanced uses on them to see the importance...
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 recursivelyint 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. }}
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
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
