Diagnosing and Resolving StackOverflowError

A recent JavaWorld Community forum message (Stack Overflow after instantiating new object) reminded me that the basics of the StackOverflowError are not always understood well by people new to Java. Fortunately, the StackOverflowError is one of the easier of the runtime errors to debug and in this blog posting I will demonstrate how easy it often is to diagnose a StackOverflowError. Note that the potential for stack overflow is not limited to Java.

Diagnosing the cause of a StackOverflowError can be fairly straightfoward if the code has been compiled with the debug option turned on so that line numbers are available in the resulting stack trace. In such cases, it is typically simply a matter of finding the repeating pattern of line numbers in the stack trace. The pattern of repeating line numbers is helpful because a StackOverflowError is often caused by unterminated recursion. The repeating line numbers indicate the code that is being directly or indirectly recursively called. Note that there are situations other than unbounded recursion in which a stack overflow might occur, but this blog posting is limited to StackOverflowError caused by unbounded recursion.

The relationship of recursion gone bad to StackOverflowError is noted in the Javadoc description for StackOverflowError that states that this Error is "Thrown when a stack overflow occurs because an application recurses too deeply." It is significant that StackOverflowError ends with the word Error and is an Error (extends java.lang.Error via java.lang.VirtualMachineError) rather than a checked or runtime Exception. The difference is significant. The Error and Exception are each a specialized Throwable, but their intended handling is quite different. The Java Tutorial points out that Errors are typically external to the Java application and thus normally cannot and should not be caught or handled by the application.

I will demonstrate running into StackOverflowError via unbounded recursion with three different examples. The code used for these examples is contained in three classes, the first of which (and the main class) is shown next. I list all three classes in their entirety because line numbers are significant when debugging the StackOverflowError.

StackOverflowErrorDemonstrator.java

package dustin.examples.stackoverflow;

import java.io.IOException;
import java.io.OutputStream;

/**
 * This class demonstrates different ways that a StackOverflowError might 
 * occur.
 */
public class StackOverflowErrorDemonstrator
{
   private static final String NEW_LINE = System.getProperty("line.separator");

   /** Arbitrary String-based data member. */
   private String stringVar = "";

   /**
    * Simple accessor that will shown unintentional recursion gone bad.  Once
    * invoked, this method will repeatedly call itself.  Because there is no
    * specified termination condition to terminate the recursion, a
    * StackOverflowError is to be expected.
    *
    * @return String variable.
    */
   public String getStringVar()
   {
      // 
      // WARNING:
      //
      // This is BAD!  This will recursively call itself until the stack
      // overflows and a StackOverflowError is thrown.  The intended line in
      // this case should have been:
      //                                  return this.stringVar;
      return getStringVar();
   }

   /**
    * Calculate factorial of the provided integer.  This method relies upon
    * recursion.
    *
    * @param number The number whose factorial is desired.
    * @return The factorial value of the provided number.
    */
   public int calculateFactorial(final int number)
   {
      // WARNING: This will end badly if a number less than zero is provided.
      //          A better way to do this is shown here, but commented out.
      //return number <= 1 ? 1 : number * calculateFactorial(number-1);
      return number == 1 ? 1 : number * calculateFactorial(number-1);
   }

   /**
    * This method demonstrates how unintended recursion often leads to
    * StackOverflowError because no termination condition is provided for the
    * unintended recursion.
    */
   public void runUnintentionalRecursionExample()
   {
      final String unusedString = this.getStringVar();
   }

   /**
    * This method demonstrates how unintended recursion as part of a cyclic
    * dependency can lead to StackOverflowError if not carefully respected.
    */
   public void runUnintentionalCyclicRecusionExample()
   {
      final State newMexico = State.buildState("New Mexico", "NM", "Santa Fe");
      System.out.println("The newly constructed State is:");
      System.out.println(newMexico);
   }

   /**
    * Demonstrates how even intended recursion can result in a StackOverflowError
    * when the terminating condition of the recursive functionality is never
    * satisfied.
    */
   public void runIntentionalRecursiveWithDysfunctionalTermination()
   {
      final int numberForFactorial = -1;
      System.out.print("The factorial of " + numberForFactorial + " is: ");
      System.out.println(calculateFactorial(numberForFactorial));
   }

   /**
    * Write this class's main options to the provided OutputStream.
    *
    * @param out OutputStream to which to write this test application's options.
    */
   public static void writeOptionsToStream(final OutputStream out)
   {
      final String option1 =
         "1. Unintentional (no termination condition) single method recursion";
      final String option2 =
         "2. Unintentional (no termination condition) cyclic recursion";
      final String option3 =
         "3. Flawed termination recursion";
      try
      {
         out.write((option1 + NEW_LINE).getBytes());
         out.write((option2 + NEW_LINE).getBytes());
         out.write((option3 + NEW_LINE).getBytes());
      }
      catch (IOException ioEx)
      {
         System.err.println("(Unable to write to provided OutputStream)");
         System.out.println(option1);
         System.out.println(option2);
         System.out.println(option3);
      }
   }

   /**
    * Main function for running StackOverflowErrorDemonstrator.
    */
   public static void main(final String[] arguments)
   {
      if (arguments.length < 1)
      {
         System.err.println(
            "You must provide an argument and that single argument should be");
         System.err.println(
            "one of the following options:");
         writeOptionsToStream(System.err);
         System.exit(-1);
      }

      int option = 0;
      try
      {
         option = Integer.valueOf(arguments[0]);
      }
      catch (NumberFormatException notNumericFormat)
      {
         System.err.println(
            "You entered an non-numeric (invalid) option [" + arguments[0] + "]");
         writeOptionsToStream(System.err);
         System.exit(-2);
      }

      final StackOverflowErrorDemonstrator me = new StackOverflowErrorDemonstrator();
      switch (option)
      {
         case 1 :
            me.runUnintentionalRecursionExample();
            break;
         case 2 :
            me.runUnintentionalCyclicRecusionExample();
            break;
         case 3 :
            me.runIntentionalRecursiveWithDysfunctionalTermination();
            break;
         default :
            System.err.println("You provided an unexpected option [" + option + "]"); 
      }
   }
}

The class above demonstrates three types of unbounded recursion: accidental and completely unintended recursion, unintended recursion associated with intentionally cyclic relationships, and intended recursion with insufficient termination condition. Each of these and their output are discussed next.

Completely Unintended Recursion

There can be times when recursion occurs with no intent of it whatsoever. A common cause might be having a method accidentally call itself. For example, it is not too difficult to get a little too careless and select an IDE's first recommendation on a return value for a "get" method that might end up being a call to that very same method! This is in fact the example shown in the class above. The getStringVar() method repeatedly calls itself until the StackOverflowError is encountered. The output will appear as follows:

Exception in thread "main" java.lang.StackOverflowError
 at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
 at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
 at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
 at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
 at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
 at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
 at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
 at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
 at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
 at 

The stack trace shown above actually is many times longer than that which I placed above, but it is simply the same repeating pattern. Because the pattern is repeating, it is easy to diagnose that line 34 of the class is the problem-causer. When we look at that line, we see that it is indeed the statement return getStringVar() that ends up repeatedly calling itself. In this case, we can quickly realize that the intended behavior was to instead return this.stringVar;.

Unintended Recursion with Cyclic Relationships

There are certain risks to having cyclic relationships between classes. One of these risks is the greater likelihood of running into unintended recursion where the cyclic dependencies are continually called between objects until the stack overflows. To demonstrate this, I use two more classes. The State class and the City class have a cyclic relationshiop because a State instance has a reference to its capital City and a City has a reference to the State in which it is located.

State.java

package dustin.examples.stackoverflow;

/**
 * A class that represents a state and is intentionally part of a cyclic
 * relationship between City and State.
 */
public class State
{
   private static final String NEW_LINE = System.getProperty("line.separator");

   /** Name of the state. */
   private String name;

   /** Two-letter abbreviation for state. */
   private String abbreviation;

   /** City that is the Capital of the State. */
   private City capitalCity;

   /**
    * Static builder method that is the intended method for instantiation of me.
    *
    * @param newName Name of newly instantiated State.
    * @param newAbbreviation Two-letter abbreviation of State.
    * @param newCapitalCityName Name of capital city.
    */
   public static State buildState(
      final String newName,
      final String newAbbreviation,
      final String newCapitalCityName)
   {
      final State instance = new State(newName, newAbbreviation);
      instance.capitalCity = new City(newCapitalCityName, instance);
      return instance;
   }

   /**
    * Parameterized constructor accepting data to populate new instance of State.
    *
    * @param newName Name of newly instantiated State.
    * @param newAbbreviation Two-letter abbreviation of State.
    */
   private State(
      final String newName,
      final String newAbbreviation)
   {
      this.name = newName;
      this.abbreviation = newAbbreviation;
   }

   /**
    * Provide String representation of the State instance.
    *
    * @return My String representation.
    */
   @Override
   public String toString()
   {
      // WARNING: This will end badly because it calls City's toString()
      //          method implicitly and City's toString() method calls this
      //          State.toString() method.
      return  "StateName: " + this.name + NEW_LINE
            + "StateAbbreviation: " + this.abbreviation + NEW_LINE
            + "CapitalCity: " + this.capitalCity;
   }
}

City.java

1 2 Page 1
Page 1 of 2