Recursion in Java

The term recursion generally refers to the technique of repeatedly splitting a task into "the same task on a smaller scale". In practice, it often means making a method that calls itself. A method called in this way is often called a recursive method. In this section, we will look at:

• how to write recursive methods in Java;
• typical uses of recursive methods;
• alternatives to recursive methods.

How to write a recursive method: listing files on a disk

A typical case where we might use recursion is for going through a structure or data that has a tree organisation. A good example is the system of files on a disk: folders can contain folders, which in turn can contain further folders etc. As a first example of recursion in Java, we'll look at how to write a program to list all the file on a particular drive (or starting at a particular folder or part of the file system). For the time being, we won't worry about problems such as eliminating duplicates, or trying to print the list "nicely" so that it resembles a tree structure (though we will look at those problems later).

When designing a recursive method, the first step is often to consider the part of the code that doesn't involve recursion. For our example of going through all the files on a disk, we might not be sure yet how to handle the part of scanning down subfolders. But what we do know is that we'll reach a point where, given a particular folder, we need to list all the files in that folder. So let's start with that bit.

To list all the files in a directory, we use part of the Java I/O API. Both files and directories (folders) in Java can be represented by a File object. And if a File object represents a directory, we can call its listFiles() method to effectively list all the files in that directory: the method returns an array of File objects, one for each of the files. So given a File object representing a directory, we want to do something like this:

public class FileLister {
  public void listFilesInDirectory(File dir) {
    File[] files = dir.listFiles();
    if (files != null) {
      for (File f : files) {
        System.out.println(f.getName());
      }
    }
  }
}

Now, we can run the above method on, say, the C: drive of a Windows computer as follows:

FileLister fl = new FileLister();
File driveRoot = new File("C:\\");
fl.listFilesInDirectory(driveRoot);

If you run the above code on your C: drive, you'll notice that it actually prints out all the files in the root of that drive, plus the directories (folders). This happens because we said that in Java, a File object reprents either a file or a directory. But actually, what we really want to do for each File object is the following:

• if it actually represents a file, we want to print its name;
• if it's a directory (folder), we want to list all the files in that directory, and the subdirectories, etc.

Luckily, File provides an isDirectory() method that we can use to find out if it is a directory (or, if not, a file). So we want to call isDirectory() on each File object. If this returns false, then we print the name; if it returns true, we want to list the files in that directory. And what do we use to print the files in that directory? Well, our listFilesInDirectory() method, of course: the method calls itself, only this time, it passes in the particular File object that we were processing inside the loop. The updated code looks as follows:

public void listFilesInDirectory(File dir) {
  File[] files = dir.listFiles();
  if (files != null) {
    for (File f : files) {
      if (f.isDirectory()) {
        listFilesInDirectory(f);
      } else {      
        System.out.println(f.getName());
      }
    }
  }
}

Now if you run the above on your C: drive, you'll see that it eventually prints out the names of all files on that drive, but not in a particularly useful or pretty way. In a real application, we'd probably want to be a bit more specific about how files were printed out. For example, we might want them printed in a way that resembled the "tree" structure of the filing system. Or we might want it to stop after it reached a directly so many levels deep. Later in this section, we'll look at how to make such modifications to the code. First, we'll consider in a bit more detail how recursion works.