“Necessary” Uses of Recursion in Imperative Langua

Question

I've recently seen in a couple of different places comments along the lines of, "I learned about recursion in school, but have never used it or felt the need for it since then." (Recursion seems to be a popular example of "book learning" amongst a certain group of programmers.)

Well, it's true that in imperative languages such as Java and Ruby[1], we generally use iteration and avoid recursion, in part because of the risk of stack overflows, and in part because it's the style most programmers in those languages are used to.

Now I know that, strictly speaking, there are no "necessary" uses of recursion in such languages: one can always somehow replace recursion with iteration, no matter how complex things get. By "necessary" here, I'm talking about the following:

Can you think of any particular examples of code in such languages where recursion was so much better than iteration (for reasons of clarity, efficiency, or otherwise) that you used recursion anyway, and converting to iteration would have been a big loss?

Recursively walking trees has been mentioned several times in the answers: what was it exactly about your particular use of it that made recursion better than using a library-defined iterator, had it been available?

[1]: Yes, I know that these are also object-oriented languages. That's not directly relevant to this question, however.

Answer 1

When you are walking any kind of tree structure, for example

• parsing a grammar using a recursive-descent parser
• walking a DOM tree (e.g. parsed HTML or XML)

also, every toString() method that calls the toString() of the object members can be considered recursive, too. All object serializing algorithms are recursive.

Answer 2

There are no "necessary" uses of recursion. All recursive algorithms can be converted to iterative ones. I seem to recall a stack being necessary, but I can't recall the exact construction off the top of my head.

Practically speaking, if you're not using recursion for the following (even in imperative languages) you're a little mad:

1. Tree traversal
2. Graphs
3. Lexing/Parsing
4. Sorting

Answer 3

Recursion can always be rewritten as iteration with an external stack. However if you're sure that you don't risk very deep recursion that would lead to stackoverflow, recursion is a very convenient thing.

One good example is traversing a directory structure on a known operating system. You usually know how deep it can be (maximum path length is limited) and therefore will not have a stackoverflow. Doing the same via iteration with an external stack is not so convenient.

Answer 4

It's all about the data you are processing.

I wrote a simple parser to convert a string into a data structure, it's probably the only example in 5 years' work in Java, but I think it was the right way to do it.

The string looked like this:

"{ index = 1, ID = ['A', 'B', 'C'], data = {" +
   "count = 112, flags = FLAG_1 | FLAG_2 }}"

The best abstraction for this was a tree, where all leaf nodes are primitive data types, and branches could be arrays or objects. This is the typical recursive problem, a non-recursive solution is possible but much more complex.

Answer 5

It was said "anything tree". I may be too cautious, and I know that stacks are big nowadays, but I still won't use recursion on a typical tree. I would, however, do it on a balanced tree.

Answer 6

In my opinion, recursive algorithms are a natural fit when the data structure is also recursive.

def traverse(node, function):
    function(this)
    for each childnode in children:
        traverse(childnode, function)

I can't see why I'd want to write that iteratively.