Java Performance Tuning

Recursion and Stacks

The techniques for converting recursive method calls to iterative ones are suitable only for methods that take a single search path at every decision node when navigating through the solution space. For more complex recursive methods that evaluate multiple paths from some nodes, you can convert a recursive method into an iterative method based on a stack. This is best illustrated with an example. I’ll use here the problem of looking for all the files with names ending in some particular string.

The following method runs a recursive search of the filesystem, printing all nondirectory files that end in a particular string:

public static String FS = System.getProperty("file.separator");
public static void filesearch1(String root, String fileEnding)
{
  File f = new File(root);
  String[] filelist = f.list( );
  if (filelist == null)
    return;
  for (int i = filelist.length-1; i >= 0; i--)
  {
    f = new File(root, filelist[i]);
    if (f.isDirectory( ))
      filesearch1(root+FS+filelist[i], fileEnding);
    else if(filelist[i].toUpperCase( ).endsWith(fileEnding))
      System.out.println(root+ls+filelist[i]);
  }
}

To convert this into an iterative search, it is not sufficient to use an extra variable to hold the current directory. At any one directory, there are several possible directories underneath, all of which must be held onto and searched, and you cannot reference them all from a plain variable. Instead, you can make that variable into a collection object. The standard object to use is a stack. ...