Quantifying Recursion on the Java Platform

January 27, 2007

As most programmers know, the solutions to many problems can be expressed very elegantly using recursion. However, it is also true that any recursive algorithm can be converted into an iterative one, and traditional wisdom suggests that iterative algorithms are preferred from the standpoint of performance and scalability.

To quantify the speed of recursion under Java 6 on Windows XP, I wrote recursive and iterative solutions to a simple tree problem: summing the values of a specified node and all its descendants. Although the superior scalability of the iterative solution is a foregone conclusion, I had expected that the speed of the iterative solution would also be faster. However, to my surprise, the speed of recursion solution proved to be significantly faster than the iterative approach.

The source code for five different solutions are listed below. It is important to note that the recursive solutions presented below are not tail-recursive, which will preclude the compiler from optimizing out the recursive method call.

Five Solutions

The first solution is recursive and also uses a Java 5 for-loop to provide code clarity.

  /**
   * Compute the sum of a tree node and its descendants recursively.
   * Use Java 5 syntax for more elegant code but more processing 
   * overhead.
   * 
   * @param root
   * @return
   */
  private static int computeSumRecursive_impl2(TreeNode root) {
    int result = root.getValue();

    for (TreeNode n: root.getChildren())
      result += computeSumRecursive_impl2(n);

    return result;
  }

  /**
   * Compute the sum of a tree node and its descendants recursively.
   * Sacrifice code elegance to maximize efficiency.
   * 
   * @param root
   * @return
   */
  private static int computeSumRecursive_impl1(TreeNode root) {
    int result = root.getValue();
    ArrayList children = root.getChildren();

    int size = children.size();
    for (int j=0; j<size; ++j) {
      result += computeSumRecursive_impl1((TreeNode) children.get(j));
    }

    return result;
  }

  /**
   * A stack-based summation routine that focuses on readability.
   * @param root
   * @return
   */
  private static int computeSumStack_impl2(TreeNode root) {
    Stack toExamine = new Stack();
    toExamine.push(root);

    int result=root.getValue();
    while (!toExamine.isEmpty()) 
      for (TreeNode n: toExamine.pop().getChildren()) {
        result += n.getValue();
        toExamine.push(n);
      }
    return result;
  }

  /**
   * A stack-based summation routine that uses loop optimization 
   * like recursive implementation 1.
   * @param root
   * @return
   */
  private static int computeSumStack_impl1(TreeNode root) {
    Stack toExamine = new Stack();
    toExamine.push(root);

    int result=root.getValue();
    while (!toExamine.isEmpty()) {
      TreeNode node = toExamine.pop();
      ArrayList children = node.getChildren();

      int size = children.size();
      for (int j=0; j<size; ++j) {
        TreeNode child = (TreeNode) children.get(j);
        result += child.getValue();
        toExamine.push(child);
      }
    }
    return result;
  }

  /**
   * A stack-based summation routine that sacrifices readability
   * and scalability to achieve maximum performance.
   * @param root
   * @return
   */
  private static int computeSumStack_impl3(TreeNode root) {
    final TreeNode[] nodeStack = new TreeNode[100];
    int start = 0;
    int end = 1;
    nodeStack[start] = root;

    int result=root.getValue();
    while (start != end) {
      ArrayList children = nodeStack[start].getChildren();
      if (++start == 100)
        start = 0;
			
      int size = children.size();
      for (int j=0; j<size; ++j) {
        TreeNode child = (TreeNode) children.get(j);
        result += child.getValue();
        if (--start < 0)
          start = 99;
        nodeStack[start] = child;
      }
    }
    return result;
  }

Performance Results and Analysis

All five solutions were tested on a balanced, 100,000 node tree with a branching factor of five. Each solution was run against the root of this tree 50 times. Timings were collected using nanoTime, and memory usage was captured using the methodology outlined in Java Tip 130: Do you know your data size? by Vladimir Roubtsov. Table 1 below summarizes the results.

On the other hand, it is also clear that it is easy to inadvertently "give away" performance by, for example, improving readability using Java 5 for-loop iteration. Elegant recursion uses over 1MB of heap space and runs almost as slowly as the fast iterative solution. The elegant iterative solution uses 160% of the fast solution's time, and uses roughly 40 times more heap space.

Some readers have questioned "why memory usage of the fast recursive solution is 0?". The reason is because it uses no heap space, which is what is measured in the example above. Rather, it relies exclusively on stack space, which places serious limits on its scalability. Had the tree used in the test not been well-balanced, the recursive solutions would have failed to run.

Clarifications

I have received a great deal of feedback on this article, and have realized that some points need clarification.

1. My intention in including the "elegant" results was not to show that the Java 5 for-loop syntax is inherently slow. However, many readers came away with that impression from the article. As many of you know, the for-loop syntax in Java 5 creates iterators behind the scenes, but, in the example presented, we can take advantage of the excellent random access capability of the child ArrayList to achieve better performance. The situtation is rather similar to autoboxing: if you, as a developer, do not understand what the compiler is doing for you, you can inadvertantly hurt application performance.
2. A number of you have pointed to the fact that Stack is backed by Vector, a synchronized collection, as the reason for the slow performance of the iterative implementations. While it is definitely contributory, it does not account for the entire performance gap, since even the "hardcore" iterative version, which does not use any collection classes at all, is slower than the fast recursive version (at least on Windows XP. Apparently the results under Java 5 on Ubuntu Linux were different).

Conclusion

As always, comments are welcome. If you happen to run the program using a different platform configuration, I would appreciate the results.