What algorithm does ROAM stand for?

I remember having to do a little prog for a class that found perfect numbers recursivly. Usually bailed between 5k and 8k calls deep. I like recursion but I don''t trust it more than a few calls deep.

I wanrned you! Didn''t I warn you?! That colored chalk was forged by Lucifer himself!

quote: Original post by BitBlt

I think he was mostly talking about recursion in games. In regular apps it doesn't really matter, in fact, some things really need recursion. Some sorts need (require is such a finalizing word) recursion. In games it may not be absolutely necessary.

You mean simple games like Pacman? Today's games, and more importantly tomorrow's games are every bit as reliant on computer science techniques as any potential app out there. Here are just some potential applications of recursion in games:
maze solving
erosion of fractal surfaces
traversing tree structures such as: octrees, skeletons, etc.
NLP
resolution theorem provers
root finders
the list goes on and on...

quote: Original post by Promiscuous Robot
That's probably true. However the original poster (cearny) was trying to decide whether or not to implement ROAM iteratively or recursively.

The decision to implement an algorithm that is inherently recursive in an iterative way is for the most part a silly proposition. Let's analyze the true cost of a recursive solution implemented using recursive function calls vs. an iterative method.

The recursive function call method incurs the cost of a function call. It is easy to conceptualize and code. The resulting code is generally small.

The iterative method requires a hand coded stack implemetation. If you argue that it does not, then it is not actually a candidate for recursion, and you had better reevaluate your understanding of recursion. Given that you have to implement a stack, you have to allocate this memory from somewhere. The allocation process takes up CPU cycles. When your program is not computing the algorithm, what is this memory doing for you. It is either doing nothing (a wasted resource) or it must released back to the OS each time we are done. This also takes CPU cycles and can result in fragmented memory. Note that when the recursive function calling method is not actually being used, the memory is automatically available because the normal stack is not being used for the recursion. Now, additionally, if you are going to use a function to maintain this hand coded stack, then you have completely defeated the purpose of it, because you are incurring a function call, the whole thing you were trying to avoid. Additionally, your code is harder to develop, harder to maintain, and more difficult to follow then the elegant recursive function call method. Might this put you off from developing the code in the first place, thus resulting in the non completion of your project? One last deficiency of the iteration method, although small, is this: If the iteration method is encoded into a dynamic link library, its larger code size will take longer to load than the recursive function call method.

quote: Original post by GKW
I remember having to do a little prog for a class that found perfect numbers recursivly. Usually bailed between 5k and 8k calls deep. I like recursion but I don't trust it more than a few calls deep.

The whole notion that recursive functions are dangerous is absurd. It is very easy, and often prudent to count the depth your recursive function has called, and set a limit to the depth it will call. This is generally standard procedure.

Note that using an iterative method, we must also monitor the height of our hand coded stack and take similar measures. The dangers are the same, and the same precautions are necessary.



Edited by - bishop_pass on November 11, 2000 10:35:31 PM

As bishop said, about 95% of the stuff in this thread is totally wrong.

Recursion is a programming tool, just like any other. The overhead of saving/restoring stack info is effectively zero. Don't even worry about it. Recursion is just like iteration in a lot of ways (indeed, so called "tail-recursion" _is_ iteration).

Recursion is perfectly useful for game programming, just like anything else. The reason you might want to exercise caution when using it, is because it can be easy for the inexperienced programmer to use it improperly. Its easy to accidentally throw in an infinite loop, or do _way_ too much work that you don't need to (ie, a naive recursive implementation of a fibonacci number/sequence generator which ends up recalculating tons of values).

If you've never used recursion before, I encourage you to learn about it. It can make many tough problems quite easy to solve.

The whole "its expensive" myth is just as bogus as all the people around here saying "oh, you should use assembly, it'll be faster" when they're dealing with a guy who has 5 nested for loops from 1 to 1000.

Edited by - daveb on November 11, 2000 10:35:16 PM

quote:
Do ROAM without recursion.
Do compiler design without recursion.
Do interpreters without recursion.
Do raytracing without recursion.
Do numerical analysis without recursion.
Do automated foliage generation without recursion.
Calculate the contributing area to a cell from a grid for water flow dynamics without recursion.
Do Hierarchical Radiosity without recursion.

yes they all require recursive techniques, but *not* recursive function calls. You can crash the machine if a function gets called too many times recursively (stack overflow...).

i.e.
QuickSort, recursive function calls is ok, becuase its on the order of log2(n) (which means it won''t every get called many times)
A recursive search on a bst probably wouldn''t be too bad either, but it could be done (significantly more efficently) without them.

Using a resursive function call to calculate, oh say, the fibinacci(sp) sequence, or perform an aggregate operation on every node of a tree (any transversal or iteration) would be a very bad place to use recursive function calls.


...
The decision whether to use recursion or not is simple.
If the problem can be solved with a recursive order less than 2, use recursion; if a recursive solution requires 2 or more recursive calls, you should not ever implement it. And they teach you that in school.

quote: Original post by Magmai Kai Holmlor

if a recursive solution requires 2 or more recursive calls, you should not ever implement it. And they teach you that in school.

Huh? Two or more recursive calls? Kind of useless, don''t you think? Read my analysis of recursion vs. iteration a few posts above.

Magmai, you'll have to forgive me, but you're completely off base here.

Almost any place where you _should_ use recursion is one where you're going to go more than 2 calls deep. If you're talking about big O notation( O(n), O(lgN), O(N^2), etc), that's something entirely different.

The decision on whether to use recursion is totally related to the problem at hand. Many times recursion will provide you with an extremely elegant solution. Other times you may as well be using a straightfoward iterative solution. In some cases, yes, there is the possibility of going crazy and going so deep in the recursive loop that you blow your stack. But you have to realize, 99.99999999% of the time this is going to be because the code was written wrong, or the problem wasn't fully understood.

Recursion is used in professional programming all the time. As far as what you're taught in school (meaning, _college_), I've never heard anyone say that. In fact, where I went to school (University of Illinois), some of the first CS classes we took were in Scheme/Lisp where recursion is used _everywhere_.

Recursion is no more dangerous, than say, using pointers. Heck, I'd say pointers are inherently more dangerous. Learn how to use recursion, you'll be glad you did.

Edited by - daveb on November 11, 2000 12:09:32 AM

Depending on how many arguments you''re throwing on the stack, I''d argue that you could easily go 10, 20, 50, or even a 100 function calls deep.

Most recursive algorithms seem to do their job quite effectively with a depth of about 8, which is essentially a zero risk of stack overflow. And in the case of modern operating systems, the stack is dynamically reallocated if a stack overflow is imminent.

Some examples of where 8 seems to usually be adequate include expression evaluation, raytracing, radiosity, fractal generation, foliage generation, root finding, etc.

To limit yourself to 2 is just plain silly. If you are going to do this, I strongly suggest you never ever ever call a function which calls a function which calls a function. In other words, don''t program.

As for the case of large trees, yes, you may need a different solution. However, there are tree balancing algorithms to keep trees from being overly large on one side.

I do not buy the idea that recursion is not used in the industry. In most cases, you are not at risk of blowing the stack. My experience with recursion: (average: 3 levels, < 100 bytes stack usage) (worst case: 20 levels, 2000 bytes stack usage) or something like that. Sure caution can be taken. But why tell someone they should try to avoid it? When dealing with things which already have a heirchal system of some kind built into their design, recursion is how to clearly represent that. The exact points bishop_pass made I learned first-hand years ago.

quote:
The decision whether to use recursion or not is simple.
If the problem can be solved with a recursive order less than 2, use recursion; if a recursive solution requires 2 or more recursive calls, you should not ever implement it. And they teach you that in school.

ridiculous. even funny. Your basically saying that when recursion can be helpful, dont use it (or have i misunderstood). Well if that works for you, then cool.

cmaker

- its not the principle. its the money.

Not a depth of 2, a branch of 2

if its a tree and your doing some sort of processing on it where you need to manipulate each node, as in the examples you gave, recursion is safe because the tree deepens logrithmically...
so you could use recursion and it would work just fine in non-realtime applications.

It if's a realtime application I'd use a threaded tree and avoid the recursion.
And quicksort aint so quick using recursion.

just implement a recursive fibinacii(sp) calculator and an iterative one, time them, then tell me I'm off base. or a factorial.
0 1 1 2 3 5 8 13 21 ...

quicksort & fib require you to call themselves twice each level of resursion. This explodes on the stack and is a bad idea.

Using recursion can be like making a function call to plot each pixel on the screen.


...
In the words of one of my math doctors "Recursion is a mathematicains tool, not a programmers."

Edited by - Magmai Kai Holmlor on November 12, 2000 1:30:37 AM