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:
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.
Matt, you should take a look at what 'tail call elimination' or 'tail recursion optimisation' is.
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.
Post a Comment