7.6 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. With this hint in mind, the method converts quite easily:

public static void filesearch2(String root, String fileEnding)
{
  Stack dirs = new Stack(  );
  dirs.push(root);
  File f;
  int i;
  String[  ] filelist;
  while(!dirs.empty(  ))
  {
    f = new File(root = (String) dirs.pop(  ));
    filelist = f.list(  );
    if (filelist =  = null)
      continue;
    for (i = filelist.length-1; i >= 0; i--)
    {
      f = new File(root, filelist[i]);
      if (f.isDirectory(  ))
        dirs.push(root+FS+filelist[i]);
      else if(filelist[i].toUpperCase(  ).endsWith(fileEnding))
        System.out.println(root+ls+filelist[i]);
    }
  }
}

In fact, the structures of the two methods are almost the same. This second iterative version has the main part of the body wrapped in an extra loop that terminates when the extra variable holding the stack becomes empty. Otherwise, instead of the recursive call, the directory is added to the stack.

In the cases of these particular search methods, the time-measurement comparison shows that the iterative method actually takes 5% longer than the recursive method. This is due to the iterative method having the overhead of the extra stack object to manipulate, whereas filesystems are generally not particularly deep (the ones I tested on were not), so the recursive algorithm is not particularly inefficient. This illustrates that a recursive method is not always worse than an iterative one.

Note that the methods here were chosen for illustration, using an easily understood problem that could be managed iteratively and recursively. Since the I/O is actually the limiting factor for these methods, there would not be much point in actually making the optimization shown. For this example, I eliminated the I/O overhead, as it would have swamped the times and made it difficult to determine the difference between the two implementations. To do this, I mapped the filesystem into memory using a simple replacement of the java.io.File class. This stored a snapshot of the filesystem in a hash table. (Actually, only the full pathnames of directories as keys, and their associated string array list of files as values, need be stored.) This kind of trickreplacing classes with another implementation to eliminate extraneous overheadis quite useful when you need to identify exactly where times are going.