Tip One:

Recursive Programming in Java

Summary

It's very easy to become too involved in prematurely optimizing Java code in terms of code size or speed. This process can result in code that is hard to read, and, therefore, difficult to maintain and debug. Follow this advice on programming explicitly to make sure your code's intent is clearly stated -- without compromising performance.

hen I write a method in Java, I try to use a form that directly and simply states the intent of the method that I am producing. This is called an explicit programming style. By using this style, not only is it easier for me to revisit and fix my code, but it is also easier for others to do so. Some may argue that when using this form, a compromise must be made in the performance of the code, but this is only true in relatively extreme circumstances such as the inner loops of heavily-used processing code.

Background
As a starting code example on which to build in our discussion below, consider the following method from a utility class that operates on the Abstract Windowing Toolkit (AWT) provided with the Java Development Kit (JDK):

1:public class Utils
2: {
3:       static public Frame GetFrame(Component c)
4:       {
5:              if(c instanceof Frame || null==c)
6:                       return c==null ? null : (Frame)c;
7:               return GetFrame(c.getParent());
8:        }
9:}

We are going to look at this method from a number of perspectives, including style, efficiency, and generalization.

First, a simple description of the method: it is responsible for finding the first Frame that contains the given AWT Component. If all of the ancestors of the specified Component are checked and a parent Frame is not found, then the method returns a null value.

To start, let's take a look at the routine line by line from the point of view of style, and to some degree from a performance point of view.

5:      if (c instanceof Frame || null==c)

You may be wondering why we first check if the component "c" is an instance of Frame, if afterward we are going to check if it is null. It seems like a strange ordering indeed, given that if the component reference is null, it cannot be an instance of a Frame! From an efficiency point of view, we know that checking an object reference for a null value takes fewer cycles than applying the instanceof operator, so reversing the order of these comparisons would allow the compiler to shortcut the "or" operation after fewer cycles, in the cases where this is appropriate.

6:    return c==null ? null : (Frame)c;

This line of code above is a bit of a disaster from a style point of view. First, it repetitious because it rechecks the validity of the component reference. Next, it uses the ternary conditional operator, a holdover from C/C++, which many people consider more difficult to read than using a standard if statement. It is also considered bad form by many programmers to use a return statement anywhere in the body of a routine except as the very last statement. These early returns can make code harder to debug, not to mention larger and more complicated in terms of the generated code than if the routine had taken the form of a clean, single return statement. Last, a null pointer is returned without an explicit cast to a Frame -- the Java compiler is left to make this cast on our behalf.

Finally,

7:      return GetFrame(c.getParent());

Generally, when a method calls itself, this is termed recursion. This particular form of recursion -- where the method calls itself as the very last expression before the return statement -- is called tail recursion since the method is "chasing its own tail" so to speak. This use of tail recursion is basically just an expression of code reuse. In other words, the routine is using recursion as a simple and "cheap" way of performing looping -- each recursive invocation of GetFrame() finds the first Frame parent, determines that we have run out of parents without ever finding a Frame, or recursively calls itself again. Unfortunately, in Java, use of recursion is expensive compared to using an explicit looping form such as while loop.

Addressing the problem
Now that we have examined some of the problem areas with this routine, let's explore ways to address each of those contentious areas.

First off, let's replace the recursion with an explicit while loop that checks for the stopping conditions described earlier. Next, we'll introduce a temporary Frame reference, which will be set inside the loop when we find the the parent Frame object. Note that we set the temporary to our default return value of null. Also notice how the new version of the routine only has a single return statement at the end.

static public Frame GetFrame(Component component)
{
Frame  resultingFrame = null;
while (component != null && resultingFrame == null)
        {
        if (component instanceof Frame) resultingFrame = (Frame)component;
        else  component = component.getParent();
        }
 return resultingFrame;
 }

Okay, for you byte counters out there, this version does result in three additional bytecode instructions than the original, recursive version has -- 19 versus 16. However, the new, explicit form never has to worry about running out of stack space -- the routine is using a single stack variable, resultingFrame, rather than relying on the method invocation stack. This explicit management of the stack data not only results in faster code in general but is also much more conducive to the optimization efforts of native Java compilers, JIT compilers, and so on.

The greatest benefit of this new, explicit version is the increased readability, simplicity, and maintainability of the code. So, we have created a version that is safer (no call stack limitations), faster (explicit looping rather than recursion), and clearer about what it's really doing.

Taking the routine a step further
We've gone this far in modifying the original, why stop here? Why don't we make the routine more useful too? In other words, why should we settle for a routine that only looks up Frame parents of a Component? Rather than writing a new routine for each type of parent that we may want to look up, let's just make the routine more generic in what it's searching for!

There are many ways to make this routine more generic. We can make it generic along a number of dimensions including the containment hierarchy and the target parent specification. In this particular case, we are going to limit this routine to sticking to the component container hierarchy but allow the caller to specify the target parent class.

First, here is an example of how you would use the new method to determine a button's parent which is an Applet.

Applet  dadApplet = (Applet)GetParent(myButton,"Applet");

In this new version we replace the use of the instanceof operator with a bit of object introspection:

static public Component GetParent(Component component, String compType )
{
Component  resultingComponent = null;
while (component != null && resultingComponent == null)
        {
          if ( compType.equals( component.getClass().getName() ) )
                        resultingComponent = component;
        else  component = component.getParent();
        }
 return resultingComponent;
 }

In terms of bytecode instructions, we have introduced one more invoking bytecode because getClass().getName() yields two "invokevirtual" calls -- whereas the statement instanceof has it own special single bytecode. Seems like a pretty reasonable tradeoff given that our routine is now a fair bit more generic.

Conclusion
So, we have taken a single utility method and gone through and cleaned it up and then extended it to be more generic and useful. In the process, we transformed the relatively slow and problematic use of tail recursion as an implicit looping construct into the faster, safer, and clearer use of the while explicit looping construct. We have also seen how minor changes to the routine made points of the code more explicit and clear.