Java Tip 62: Explicit and recursive programming in Java

Use Java style and idioms to ease maintenance without sacrificing performance

By Nige Warren With John D. Mitchell, JavaWorld.com, 10/01/98

Background

As a starting code example on which to build in our discussion below, consider the following method from a utilitty 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.