Sunday, December 17, 2006

Recursion vs. Loop

Problem

Imagine that your application is meant to process an XML file. It is given a tag and needs to find a "special tag" that this tag might be nested in. This problem has several solutions. I tackled a similar problem some time ago and I will present you with some of the solutions that I considered.

While loop

private SpecialTag findSpecialTag()
{
Tag parent = this.getParentTag();
while (parent != null && !(parent instanceof SpecialTag))
{
parent = parent.getParentTag();
}
return (SpecialTag) parent;
}

Do-while loop

private SpecialTag findSpecialTag()
{
Tag parent = this;
do
{
parent = parent.getParentTag();
}
while (parent != null && !(parent instanceof SpecialTag));
return (SpecialTag) parent;
}

Recursion

private SpecialTag findSpecialTag()
{
return findSpecialTag(this.getParentTag());
}

private SpecialTag findSpecialTag(Tag tag)
{
if (tag == null || tag instanceof SpecialTag)
{
return (SpecialTag) tag;
}
else
{
return findSpecialTag(tag.getParentTag());
}
}

Solution

In my personal opinion, I find the while loop cleanest and simplest to understand. Do-while loop gets a bit messy with the condition at the end and recursion is probably the worst. I find recursion a bit hard to follow. It can also introduce an extra method just for its own sake (as in this example).

I do not have a strong opinion on this topic. If you like to program recursions, while loops, do-while loops, or for loops, it's fine by me. I certainly will not change your code, but if you ask me to write some code, it'd most likely be a while (or for) loop.

I use while and for loops interchangeably. The previous example with while loop would look like this with for loop:

private SpecialTag findSpecialTag()
{
Tag p = this.getParentTag();
for(; p != null && !(p instanceof SpecialTag); p = p.getParentTag());
return (SpecialTag) parent;
}

What is your preference?

3 comments:

Matt Ryall said...

I am not a functional programmer (IANAFP), but I tend to avoid recursion for three reasons:

1. Small mistakes can lead to catastrophic failures with stack overflow or other resource consumption problems. This can happen with loops, but the problems are usually more obvious. Locking in reentrant code is one particular bugbear, although fortunately Java monitors don't have this problem.

2. Complex recursive routines, as you rightly say, can hinder understanding the code.

3. Less important: a loop is faster than a method call because it doesn't need to store another stack frame. I'm not sure how much difference this really makes in practice.

Even though I've listed three benefits of loops over recursion, there are times when rewriting a recursive function as a loop can be difficult and lead to more complex code.

The performance question isn't as important in my mind as the question of readability and reduced complexity. Go for the simplest solution that works.

Ricky Clarkson said...

Matt, you should take a look at what 'tail call elimination' or 'tail recursion optimisation' is.

Matt said...

Ricky, which problem in my list does optimising tail recursion help?

I understand the point for performance enhancement of recursive code in compiling, but not how it's relevant to making the code simpler.


Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License.