Practical Uses of Recursion

[Ancient Dragon]

For those of you who have been working for some time I'd like to find out what practical uses you have seen for recursion. I'm not talking about college courses or what you see in tutorials, but what programmers use it for in real-world programs such as system, applications, etc.

There are only three reasons that I have ever used it in my c or c++ programs To navigate through disk directory trees
Parse binary trees
Some sorting algorithms

Can you add to the above list?

[Narue]

>what programmers use it for in real-world programs such as system, applications, etc.
Recursive descent parsing comes to mind.

>Parse binary trees
Actually, my experience is that nearly every recursive algorithm when working with binary trees is better written iteratively. This improves the performance[1], footprint guarantees[2], reliability[3], and flexibility[4].

[1] Removal of recursion is one of the first steps in optimizing a recursive algorithm.
[2] It's harder to guess how much memory will be used when variable stack frames enter the picture.
[3] Unless the height of the tree is limited to below the remaining stack size at the point where recursion begins (imagine trying to guarantee this), the possibility of a stack overflow is always going to be present.
[4] A good example of this is re-entrant iteration. I have yet to see a good way to break off recursive iteration and then start it back at the same place (without coroutine support, of course), or change the direction in which you traverse the tree mid-traversal (at least, not without being painfully ugly). With an iterative approach, both of these (very useful) tasks are trivial.

[sarehu]

[4] A good example of this is re-entrant iteration. I have yet to see a good way to break off recursive iteration and then start it back at the same place (without coroutine support, of course)

Pass a function as an argument and call that.

[Narue]

>Pass a function as an argument and call that.
By "good way", I meant something that's both easy to use and easy to follow, as well as works across the board without changes. Your suggestion only works for very specific cases and does not scale well.

[sarehu]

That's easy to use and easy to follow, and works across the board. What do you mean "does not scale well." Are you babbling nonsensically? I don't understand how you think the statements you are making are true.

Oh, and AD, another example of recursion is when you have some shallow hierarchy of things like windows and you want to set their sizes.

[Salem]

Recursion is never(*) used in embedded systems because of the indeterminate amount of stack space required.

A stack overrun on an embedded platform just trashes something else, rather than killing the runaway process with an out-of-stack exception.
Stacks are also of a fixed size; there's no VM to extend the space if you need it.

[sciwizeh]

the "paint bucket" or "fill" tool of graphics editors sometimes use recursion. although as has already been stated, when stack space is a problem non-recursive methods are used.

the algorithm i found for parsing a mathematical expressions form strings was recursive, i found it in a book after no one in the java forum had a solution i posted the code onto the thread . it was the only way i found that didn't either use a third party generator or library to parse math. i am sure there are other ways though. i just can't find them.

[sarehu]

the "paint bucket" or "fill" tool of graphics editors sometimes use recursion. although as has already been stated, when stack space is a problem non-recursive methods are used.

Yuck. I was going to say that a queue was infinitely better than recursion, but even a queue is pretty bad.

[sciwizeh]

i couldn't do recursion Java didn't have enough stack space i used arraylist. it's not visibly slow either.