Recursion is a very important feature of many a programming language. Recursion simply means a method calling itself. This may sound a little "disturbing" to any budding programmer but it is a very important attribute of the Java programming language. One may assume that this will result in endless method calls. Technically speaking, that is right. Recursion may indeed result in endless method calls that culminate in rapid consumption of memory that may even humble some more powerful computers out there. However, this problem is a result of progressive method calls not manipulating a parameter towards the base case upon which the method calls terminate. Recursion is a very important feature of Java that some tasks may not be as effectively executed using other technics. Take the case of opening a directory, printing the contents of that directory. That parent directory may also contain other directories (sub-directories) whose contents need to be printed out and so on. Recursion performs this task very quickly and easily. Practical examples of the use of
recursion are the tree or ls command line utility in most operating systems that displays the contents of a directory and virus scanners that deploy a similar mechanism to scan files and directories for viruses and any other malware. It allows a method to continually call itself until the parameter matches the specified base case wherein the recursive method calls end.
For a recursive operation to eventually complete, each time a recursive method calls itself, it manipulates its arguments so that the arguments gradually increment/ decrement or transform to a value that is comparatively similar to that of the base case. At that point, the method recognizes the base case and returns
a result to the previous copy of the method. A sequence of returns ensues until the original method call returns the final result to the caller. When a method calls itself, it passes arguments (parameters) which the called method (itself) first compares to a base case. If it does not match, the method executes it causes the problem being dealt with to become simpler (for example decrement the passed parameter) which itself will be passed as an argument yet again to the method. A little confusing, huh? Once you get round and understand this, you will appreciate the power of recursion.
I have created a simple program that is similar to the Microsoft Windows Command prompt feature "tree" with its extensions "tree /f" which display the sub-directories only or sub-directories with their contents of a parent directory. It is also similar to the "ls" feature of other NIX based operating systems. It consists of the following files;
- FileIterator.java
- IsDirectory.java
- IsNotDirectory.java
The program first opens a directory, then prints out the contents; first printing out the files first then the sub-directories, opening the sub-directories and printing out their contents (sub-directories and files) and so on.
The program makes use of two utility classes that determine if the given directory content is a file or a directory. The program is able to accomplish the following tasks;
- Command line option that allows the user to specify whether
files and directories should be written out or just directories. - Indents the contents of every directory and sub-directories
- Add the number of files and total size of those files in each
directory in brackets after each directory name.
//FileIterator.java
package com.blogspot.emmanueltoko;
import java.io.File;
import java.io.IOException;
import java.util.Scanner;
/**
* Class prints out the all the sub-directories and files of a directory
* It calls utility methods recursively to open and printout the contents of a
* directory. Each directory as well as its sub-directories have their size on
* disk printed out as well as the number of files or contents contained therein
*
* @author Emmanuel Toko
*/
public class FileIterator
String indent = ""; //indentation initially not set
public static void main(String[] args)
{
File rootFolder = new File(
"C:/Program Files");
FileIterator fi = new FileIterator();
//Used to read input from keyboard in console
Scanner input = new Scanner(System.in);
//variable to store the option entered from keyboard
String selection = null;
//Keep asking for input until the user enters input of any type
do
{
System.out.print(
"\nEnter 'tree' to output directories only\n" +
" or 'tree /f' to output directories and files: ");
selection = input.next().trim();
} while (input == null);
System.out.println();
//Check user input to determine next course of action
if (selection.equals("tree"))
{
fi.printDirectories(rootFolder, "");
System.out.println(
"\nScouring of given directories complete!!");
System.out.println();
}//End of if statement block
else if (selection.equals("tree /f"))
{
fi.printContents(rootFolder, "");
System.out.println(
"\nScouring of given directories complete!!");
System.out.println();
} //End of else if statement block
else
{
System.out.println("\nYou did not enter either option");
System.out.println("Application will now exit");
System.exit(0);
} //End of else statement block
}//End of method main
/**
* Method prints out both directories and files contained in the given
* abstract path
* Method print out files first then sub-directories after
* @param folder - File object parameter with the path of the directory to
* be scoured.
* @param ind - String parameter with the given indentation so that files
* and sub-directories are printed some spaces to the right
* of the parent directory
*/
public void printContents(File folder, String ind)
{
/*
* Make attempt to read the directory contents and print them out
* However some exceptions may be thrown such as inability to
* open a directory
*/
try
{
//First determine whether folder parameter is a file
File[] files = folder.listFiles(new IsNotDirectory(folder));
for(int i=0; i < files.length; i++)
{
System.out.print(indent + " ");
System.out.printf("%s%n", files[i].getName());
}//End of for statement block
//Check if folder argument is a directory
File[] directorys = folder.listFiles(new IsDirectory(folder));
for(int i = 0; i < directorys.length; i++)
{
indent = ind + " ";
System.out.print(indent);
long fileSize = getSize(directorys[i]);
int fileNum = directorys[i].listFiles().length;
/*
* 1024 bytes make a KiloByte. The additional
* zeros are to let Java treat this variable as a
* long and not an int value
*/
System.out.printf(
"%s (Directory Size: %.2f KB %s)%n"
, directorys[i].getName(),
fileSize/1024.00, "| Number of files: " +
fileNum);
printContents(directorys[i], indent);
} //End of for statement block
}//End of try statement block
catch (Exception ex) //catch any unexpected exceptions
{
System.out.println("Exception encountered: " +
ex.getMessage());
} //End of catch statement block
} //End of method printContents
/**
* Method prints out only sub-directories given the path
*
* @param folder - File object parameter with the path of the directory to
* be scoured.
* @param ind - String parameter with the given indentation so that files
* b-directories are printed some spaces to the right
* of the parent directory
*/
public void printDirectories(File folder, String ind)
{
try
{
File[] directorys = folder.listFiles(new IsDirectory(folder));
for(int i = 0; i < directorys.length; i++)
{
indent = ind + " ";
System.out.print(indent);
long fileSize = getSize(directorys[i]);
int fileNum = directorys[i].listFiles().length;
System.out.printf("%s (Directory Size: %.2f KB %s)%n",
directorys[i].getName(),
fileSize/1024.00, "| Number of files: " +
fileNum);
printDirectories(directorys[i], indent);
}//End of for statement block
}//End of try statement block
catch (Exception ex) //Catch any kind of exception that may be thrown
{
System.out.println("Exception: " + ex.getMessage());
} //End of Exception catch statement block
} //End of method printContents
/**
* Utility method that returns the size of the given directory. The size
* returned is a variable long but is the actual number of bytes of the
* directory. This method however returns -1 if an IOException is thrown.
*
* @param file a File object representing a file or directory.
* @return the size of the given file or directory as a long value.
*/
public long getSize(File directory)
{
long size = 0;
if(directory.isDirectory())
{
File[] files = directory.listFiles();
if(files != null)
{
for(int i = 0; i < files.length; i++)
{
long tmpSize = getSize(files[i]);
if(tmpSize != -1)
{
size += tmpSize;
}//End of inner if statement block
}//End of for statement block
return size;
}//End of outer if statement block
return -1; //return -1 if given path does not exist
}//End of outer most if statement block
return directory.length();
}//End of method getSize
}//End of class FileIterator
The File class does not have a method of directly determining the size of a directory. Calling the getSize() method on a File object representing a directory won't give a sensible result as it does on a File object representing an actual file on disk.
Calls to method getSize() of class FileIterator should be able to handle that.
The IsDirectory class determines whether a given parameter of reference type File is a directory.
This class implements the FileFilter interface of package java.io which is a filter for abstract pathnames. Instances of this interface may be passed to the listFiles(FileFilter) method of the File class. This interface has only one method (which is overridden here) accept. This method tests whether or not the specified abstract pathname should be included in a pathname list.
Its parameter: pathname is a File reference variable that is the abstract pathname to be tested. It returns true if and only if pathname should be included.
//IsDirectory.java
package com.blogspot.emmanueltoko;
import java.io.FileFilter;
import java.io.File;
public class IsDirectory implements FileFilter
{
private File file;
public IsDirectory(File file)
{
this.file = file;
}//End of one argument constructor
@Override
public boolean accept(File file)
{
if (file.isDirectory())
{
return true;
}//End of if statement block
else
{
return false;
}//End of else statement block
}//End of overridden method accept
}//End of class IsDirectory
The IsNotDirectory class determines whether a given parameter of reference type File is a file. This class implements the FileFilter interface of package java.io which is a filter for abstract pathnames. Instances of this interface may be passed to the listFiles(FileFilter) method of the File class. This interface has only one method (which overridden here) accept. This method tests whether or not the specified abstract pathname should be included in a pathname list.
s parameter: pathname is a File reference variable that is the abstract pathname to be tested. It returns true if and only if pathname should be included.
IsNotDirectory.java
package com.blogspot.emmanueltoko;
import java.io.FileFilter;
import java.io.File;
public class IsNotDirectory implements FileFilter
{
private File file;
public IsNotDirectory(File file)
{
this.file = file;
} //End of one argument constructor
@Override
public boolean accept(File file)
{
if (file.isFile())
{
return true;
} //End of if statement block
else
{
return false;
}//End of else statement block
}//End of overridden method accept
}//End of class IsNotDirectory
The code has largely been well documented and so things should be clear and easily understood without alot of elaboration. Note: When you run this code directly without any modifications on Windows all will be well. However, for any other operating system or just to scan any parent folder, you many make changes to the argument to the rootFolder File constructor to your preference. If you have installed many programs, you will be inundated with many scrolling directory and file names.
There are some features of recursion that you will quickly notice if you run this program on a not so powerful computer. When you the parent directory whose contents are to be scoured contains very many contents(for example, the directory containing the the Java API documentation(if you have downloaded it)) you will notice that after the parent directory name is printed out, it may take a few seconds of inactivity before the number of files and the size of the directory is printed out.This is so because of the further recursive calls to the methods printDirectories() and getSize which first scan to the last
sub-directory of a given directory and determining the file sizes and summing them progressively before the number of files and the parent directory size are printed out. I developed and run this program on a Compaq Deskpro Pentium II 370 MHz desktop computer(incredible, huh? but yes that computer can handle Java JDK 6 without even breaking a sweat). You probably won't want to install NetBeans or Eclipse on this computer though.
