Using Recursion

Recursion is a basic programming technique in which a method calls itself to solve some problem. A method that uses this technique is called recursive. Many programming problems can only be solved by recursion, and some problems that can be solved by other techniques are better solved by recursion.

TECHNICAL STAUFF 

I'm not sure, but I think the term recursion comes from the Latin recurse, recurset, recursum, which means to curse repeatedly. I do know that that's exactly what many programmers feel like when struggling with complex recursive programming problems.

True, sometimes the concept of recursion can get a little tricky. Many programmers steer clear of it, looking for other techniques to solve the problem at hand. And in many cases, a non-recursive solution is best. However, many problems just cry out for recursion.

The Classic Factorial Example

One of the classic problems for introducing recursion is calculating the factorial of an integer. The factorial of any given integer-I'll call it n so I sound mathematical-is the product of all the integers from 1 to n. Thus the factorial of 5 is 120: 5 times 4 times 3 times 2 times 1.

The non recursive solution

You don't have to use recursion to calculate factorials. Instead, you can use a simple for loop. For example, here's a method that accepts an int number and returns the number's factorial as a long:

private static long factorial(int n)
{
 long f = 1;

 for (int i = 1; i <=n; i++)
 f = f * i;
 return f;
}

This method just uses a for loop to count from 1 to the number, keeping track of the product as it goes. Here's a snippet of code that calls this method and displays the result:

int n = 5;
long fact;
fact = factorial(n);
System.out.println("The factorial of "+ n + " is "
 + fact + ".");

If you run this code, the following line is displayed on the console:

The factorial of 5 is 120.

Warning 

Factorials get big fast. You should use a long rather than an int to calculate the result. And you should use the NumberFormat class to format the result. For example, if int is 20 instead of 5, the previous code prints this on the console:

The factorial of 20 is 2432902008176640000.

If you use the NumberFormat class to format the result, the console output is more readable:

The factorial of 20 is 2,432,902,008,176,640,000.

The recursive solution

The non-recursive solution to the factorial problem works, but it isn't much fun. The recursive solution is based on the notion that the factorial for any number n is equal to n times the factorial of n −1, provided that n is greater than 1. If n is 1, the factorial of n is 1.

This definition of factorial is recursive because the definition includes the factorial method itself. It also includes the most important part of any recursive method: an end condition. The end condition indicates when the recursive method should stop calling itself. In this case, when n is 1, I just return 1. Without an end condition, the recursive method keeps calling itself forever.

Here's the recursive version of the factorial method:

private static long factorial(int n)
{
 if (n == 1)
 return 1;
 else
 return n * factorial(n-1);
}

This method returns exactly the same result as the version in the previous section, but it uses recursion to calculate the factorial.

One way to visualize how recursion works is to imagine that you have five friends, named Jordan, Jeremy, Jacob, Justin, and Bob. Your friends aren't very smart, but they're very much alike. In fact, they're clones of each other. Cloning isn't a perfect process yet, so these clones have limitations. Each can do only one multiplication and can ask one of its clones one question.

So you walk up to Jordan and say, "Jordan, what's the factorial of five?"

Jordan says, "I don't know, but I do know it's five times the factorial of four. Jeremy, what's the factorial of four?"

Jeremy says, "I don't know, but I do know it's four times the factorial of three. Jacob, what's the factorial of three?"

Jacob says, "I don't know, but I do know it's three times the factorial of two. Justin, what's the factorial of two?"

Justin says, "I don't know, but I do know it's two times the factorial of one. Hey, Bob! What's the factorial of one?"

Bob, being the most intelligent of the bunch on account of not having a J-name, replies, "Why, one, of course." So he tells his answer to Justin.

Justin says, "Ah! Two times one is two." So he tells the answer to Jacob.

Jacob says, "Thanks. Three times two is six." Jacob tells his answer to Jeremy.

Jeremy says, "Dude! Four times six is 24." Jeremy tells his answer to Jordan.

Jordan says, "Very good! Five times 24 is 120." So he tells you the answer.

That's pretty much how recursion works.

Displaying Directories

Recursion lends itself well to applications that have to navigate through directory structures, such as a Windows or Unix file system. In a file system, a directory is a list of files and other directories. Each of those directories is itself a list of files and other directories, and so on. Directories can be snugly nestled inside of other directories and have no limit in number.

Listing 4-1 shows a program that uses a recursive method to list all the directories that are found starting from a given path. I use indentation to show the directory structure. For example, here's the console output for the directories I used to organize the documents for this book:

Welcome to the Directory Lister
Enter a path: C:Java AIO

Listing directory tree of:
C:Java AIO
 Apps
 Book 1
 Book 2
 Book 3
 Book 4
 Book 5
 Manuscript
 Book 1
 Book 2
 Book 3
 Book 4
 Book 5
 Front
 Plans
Another? (Y or N) n

Well, as you can see, I haven't done Books VI through IX yet. By the time you read this chapter, there will be even more directories to list!

Warning 

Don't enter c: unless you're prepared to wait a long time for the program to finish listing all the directories on your hard drive.

The Directory Listing application is remarkably simple. Before I explain its details, though, I want to point out that this program uses the File class, which is part of the java.io package. The File class represents a single file or directory. You find out much more about this class in Book VIII. For now, you just need to know these five details:

• The constructor for this class accepts a directory path as a parameter and creates an object that represents the specified directory.
• You can use the exists method to find out if the directory specified by the path parameter exists.
• The listFiles method returns an array of File objects that represent every file and directory in the current File object.
• The isDirectory method returns a boolean that indicates whether or not the current File object is a directory. If this method returns false, you can assume the File object is a file.
• The getName method returns the name of the file.

Listing 4-1: The Directory Listing Application

import java.io.File; → 1
import java.util.Scanner;

public class DirList
{
 static Scanner sc = new Scanner(System.in);

 public static void main(String[] args)
 {
 System.out.print(
 "Welcome to the Directory Lister");
 do
 {
 System.out.print("
Enter a path: ");
 String path = sc.nextLine(); → 15
 File dir = new File(path); → 17
 if (!dir.exists() || !dir.isDirectory()) → 18
 System.out.println(
 "
That directory doesn't exist.");
 else
 {
 System.out.println(
 "
Listing directory tree of:");
 System.out.println(dir.getPath()); → 25
 listDirectories(dir, " "); → 26
 }
 } while(askAgain()); → 28
 }

 private static void listDirectories( → 31
 File dir, String indent)
 {
 File[] dirs = dir.listFiles(); → 34
 for (File f : dirs) → 35
 {
 if (f.isDirectory()) → 37
 {
 System.out.println(
 indent + f.getName()); → 40
 listDirectories(f, indent + " "); → 41

 }
 }
 }

 private static boolean askAgain()
 {
 System.out.print("Another? (Y or N) ");
 String reply = sc.nextLine();
 if (reply.equalsIgnoreCase("Y"))
 return true;
 return false;
 }
}

The following paragraphs point out the highlights of how this program works:

→ 1	This import statement is required to use the File class.
→ 15	A Scanner object is used to get the pathname from the user.
→ 17	The pathname is passed to the File class constructor to create a new File object for the directory entered by the user.
→ 18	The exists and isDirectory methods are called to make sure the path entered by the user exists and points to a directory rather than a file.
→ 25	If the user entered a good path, the getPath method is called to display the name of the path represented by the File object. (I could just as easily have displayed the path variable here.)
→ 26	The listDirectories method is called to list all the subdirectories in the directory specified by the user.
→ 28	The user is asked whether he or she wants to list another directory, and the loop repeats if the user enters Y.
→ 31	This is the start of the listDirectories method. This method takes two parameters: a File object representing the directory to be listed and a String object that provides the spaces used to indent each line of the listing. When this method is first called from the main method, the indentation is set to two spaces by a string literal.
→ 34	The listFiles method is called to get an array of all the File objects in this directory.
→ 35	An enhanced for loop is used to process all the File objects in the array.
→ 37	This if statement checks to see if a file is a directory rather than a file.
→ 40	If the File object is a directory, the indentation string is printed, followed by the name of the directory as returned by the getName method.
→ 41	Next, the listDirectories method is called recursively to list the contents of the f directory. However, two spaces are added to the indentation string so that any directories in the f directory are indented two spaces to the right of the current directory.

Open table as spreadsheet

If you're having trouble understanding how the recursion in this program works, think of it this way: The listDirectory method lists all the subdirectories in a single directory. For each directory, this method does two things: (1) prints the directory's name, and (2) calls itself to print any subdirectories of that directory.

Tip 

Previously, I mentioned that all recursive methods must have some type of condition test that causes the method to stop calling itself. In this program, the condition test may not be obvious. However, eventually the listDirectories method is passed a directory that doesn't have any subdirectories. When that happens, the recursion ends-at least for that branch of the directory tree.

Writing Your Own Sorting Routine

The world is full of Computer Science majors who don't know anything more about computers than you do. However, they once attended a class in which the instructor explained how sorting algorithms worked. They may have received a C in that class, but it was good enough to graduate.

Now you have a chance to learn what you missed by not majoring in Computer Science. I'm going to show you how one of the most commonly used sorting techniques actually works. It's called Quicksort, and it's a very ingenious use of recursion. I even show you a simple Java implementation of it.

TECHNICAL STAUFF 

Quicksort is easily the most technical part of this entire book. If you never wanted to major in Computer Science (and if you don't even want to talk to people who did), you may want to just skip the rest of this chapter now.

For most of us, learning how sorting algorithms such as Quicksort work is merely an intellectual exercise. The Java API has sorting already built in-for example, check out the Arrays.sort method. Those sort routines are way better than any that you or I will ever write.

Understanding how Quicksort works

The Quicksort technique sorts an array of values by using recursion. Its basic steps are this:

1. Pick an arbitrary value that lies within the range of values in the array.

   This value is the pivot point. The most common way to choose the pivot point is to simply pick the first value in the array. Folks have written doctoral degrees on more sophisticated ways to pick a pivot point that results in faster sorting. I like to stick with using the first element in the array.

2. Rearrange the values in the array so that all the values that are less than the pivot point are on the left side of the array and all the values that are greater than or equal to the pivot point are on the right side of the array.

   The pivot value indicates the boundary between the left side and the right side of the array. It probably won't be dead center, but that doesn't matter. This step is partitioning, and the left and right sides of the arrays are partitions.

3. Now treat each of the two sections of the array as a separate array, and start over with Step 1 for that section.

   That's the recursive part of the algorithm.

The hardest part of the Quicksort algorithm is the partitioning step. This step must rearrange the partition so that all values that are smaller than the pivot point are on the left, and all elements that are larger than the pivot point are on the right. For example, suppose the array has these ten values:

38 17 58 22 69 31 88 28 86 12

Here the pivot point is 38, and the task of the partitioning step is to rearrange the array to something like this:

17 12 22 28 31 38 88 69 86 58

Notice that the values are still out of order. However, the array has been divided around the value 38: All values that are less than 38 are to the left of 38, and all values that are greater than 38 are to the right of 38.

Now you can divide the array into two partitions at the value 38 and repeat the process for each side. The pivot value itself goes with the left partition, so the left partition is this:

17 12 22 28 31 38

This time, the partitioning step picks 17 as the pivot point and rearranges the elements as follows:

12 17 22 28 31 38

As you can see, this portion of the array is now sorted. Unfortunately, Quicksort doesn't realize that at this point, so it takes a few more recursions to be sure. But that's the basic process.

The sort method

The actual code that drives a Quicksort routine is surprisingly simple:

public static void sort(int low, int high)
{
 if (low >= high)
 return;
 int p = partition(low, high);
 sort (low, p);
 sort (p+1, high);
}

This method sorts the portion of an array indicated by the low and high index values passed to it. Ignoring the if statement for now, the sort method works by calling a partition method. This method rearranges the array into two sections called partitions so that all the values in the left partition are smaller than all the values in the right partition. The partition method returns the index of the end of the left partition. Then the sort method calls itself twice: once to sort the left partition, and then again to sort the right partition.

To get the sort started, you call it with zero as the low value and the array length and 1 as the high value. Thus the sort method begins by sorting the entire array. Each time the sort method executes, it calls itself twice to sort smaller partitions of the array.

The if statement at the beginning of the sort method compares the low value with the high value. If the low value is equal to or greater than the high value, the partition has only one element (or perhaps no elements) and is therefore already sorted. In that case, the sort method simply returns without calling itself again. That's the condition that ends the recursion.

The partition method

The sort method itself is the simple part of the Quicksort technique. The hard part is the partition method. This method accepts two parameters: the low and high indexes that mark the portion of the array that should be sorted. The basic outline of the partition method goes something like this:

1. Pick a pivot point.
2. Move all elements that are less than the pivot point to the left side of the partition.
3. Move all elements that are greater than the pivot point to the right side of the partition.
4. Return the index of the pivot point.

The most commonly used technique for partitioning the array is to maintain two index variables, named i and j, that work from both ends of the array toward the center. First, i starts at the beginning of the array and moves forward until it encounters a value that's greater than the pivot value. Then j starts at the opposite end of the array and moves backward until it finds a value that's less than the pivot point. At that point, the partition method has a value that's greater than the pivot point on the left side of the array and a value that's less than the pivot point on the right side of the array.

So it swaps them.

Then it repeats the cycle: i is incremented until it finds another value that's greater than the pivot value, j is decremented until it finds another value that's less than the pivot value, and the elements are swapped. This process repeats until j is less than i, which means the indexes have crossed and the partitioning is done.

Now put it together in some code:

public static int partition(int low, int high)
{
 int pivot = a[low];

 int i = low - 1;
 int j = high + 1;

 while (i < j)
 {
 for (i++; a[i] < pivot; i++);
 for (j--; a[j] > pivot; j--);
 if (i < j)
 swap(i, j);
 }
 return j;
}

Note that in this code, the array being sorted is a static int array named a. The low and high ends of the partition to be partitioned are passed in as parameters, and the method starts by choosing the first element in the partition as the value for the pivot point. Next, it initializes the index variables i and j from the parameters. Notice that 1 is subtracted from the low value and that 1 is added to the high value. The index variables take one step back from the array before the looping starts so they can get a good start.

The while loop is used to indicate when the partitioning is finished. It repeats as long as i is less than j. After these index variables stop, the partitioning is done, and the value of j is returned to indicate the index point that divides the left partition from the right partition.

In the body of the while loop are two strange bodyless for loops. These for loops don't have bodies because their only purpose is to move their index values until they find a value that's either less than or greater than the pivot value.

The first for loop increments the i index variable until it finds a value that's greater than the pivot point. This for loop finds the first value that might need to be moved to the other side of the array.

Next, the second for loop decrements the j index variable until it finds a value that's less than the pivot point. So this loop finds a value that may need to be swapped with the value found by the first for loop.

Finally, the if statement checks whether the indexes have crossed. Assuming they haven't, a swap method is called to swap the elements. The swap method is mercifully simple:

public static void swap(int i, int j)
{
 int temp = a[i];
 a[i] = a[j];
 a[j] = temp;
}

This method moves the i element to a temporary variable, moves the j element to the i element, and then moves the temporary variable to the j element.

Putting it all together

Now that you've seen the basic steps necessary to create a Quicksort program, Listing 4-2 shows a program that gives these methods a workout. This program creates an array of 100 randomly selected numbers with values from 1 through 100. It prints the array, uses the sorting methods shown in the previous sections to sort the array, and then prints the sorted array. Here's a sample run:

Unsorted array:

65 51 38 47 93 87 50 36 77 58 22 92 46 60 49 90 28 39 27 8
66 76 40 99 90 35 34 30 7 41 45 34 41 17 36 63 52 65 50 77
 2 93 48 6 91 67 34 69 33 47 50 12 88 15 65 40 29 74 34 14
55 37 28 25 98 66 69 88 66 27 29 88 29 87 9 29 77 32 4 11
68 40 17 61 50 90 24 1 59 91 69 5 82 69 51 45 29 38 61 86

Sorted array:

 1 2 4 5 6 7 8 9 11 12 14 15 17 17 22 24 25 27 27 28
28 29 29 29 29 29 30 32 33 34 34 34 34 35 36 36 37 38 38 39
40 40 40 41 41 45 45 46 47 47 48 49 50 50 50 50 51 51 52 55
58 59 60 61 61 63 65 65 65 66 66 66 67 68 69 69 69 69 74 76
77 77 77 82 86 87 87 88 88 88 90 90 90 91 91 92 93 93 98 99

As you can see, the first array is in random order, but the second array is nicely sorted.

Listing 4-2: A Sorting Program

public class QuickSortApp
{
 public static void main(String[] args)
 {
 int LEN = 100;
 int[] unsorted = new int[LEN];
 for (int i = 0; i→ 7
 unsorted[i] =
 (int)(Math.random() * 100) + 1;
 System.out.println("Unsorted array:");
 printArray(unsorted); → 10
 int[] sorted = sort(unsorted); → 11
 System.out.println("

Sorted array:");
 printArray(sorted); → 13
 }

 private static void printArray(int[] array) → 16
 {
 System.out.println();
 for (int i = 0; i < array.length; i++)
 {
 if (array[i] < 10)
 System.out.print(" ");
 System.out.print(array[i] + " ");

 if ((i+1) % 20 == 0)
 System.out.println();
 }
 }

 private static int[] a; → 29
 public static int[] sort(int[] array) → 31
 {
 a = array;
 sort(0, a.length - 1);
 return a;
 }

 public static void sort(int low, int high) → 38
 {
 if (low >= high)
 return;
 int p = partition(low, high);
 sort (low, p);
 sort (p+1, high);
 }

 public static int partition(int low, int high) → 47
 {
 int pivot = a[low];

 int i = low - 1;
 int j = high + 1;

 while (i < j)
 {
 for (i++; a[i] < pivot; i++);
 for (j--; a[j] > pivot; j--);
 if (i < j)
 swap(i, j);
 }
 return j;
 }

 public static void swap(int i, int j) → 64
 {
 int temp = a[i];
 a[i] = a[j];
 a[j] = temp;
 }
}

Most of the code in this program has already been explained, so I just point out a few of the highlights here:

→ 7	This for loop assigns 100 random values to the array.
→ 10	The printArray method is called to print the unsorted array.
→ 11	The sort method is called to sort the array.
→ 13	The printArray method is called again to print the sorted array.
→ 16	The printArray method uses a for loop to print array elements. Each element is separated by two spaces. However, an additional space is printed before each element if the element's value is less than 10. That way the values line up in columns. Also, the remainder operator (%) is used to call the println method every 20 elements. Thus, this method prints five lines with 20 values on each line. (The last few values in the array won't line up exactly if they happen to be 100, but that's okay.)
→ 29	A static variable named a is used to hold the array while it is being sorted.
→ 31	The sort method has two versions. The first accepts an int array as a parameter and returns an int array with the sorted values. This method sets the static a variable to the array passed via the parameters, calls the second version of the sort method to sort the entire array, and then returns the sorted array.
→ 38	This is the second sort method. It sorts the partition indicated by the parameters. (The operation of this method is explained in detail in the section titled "The sort method.")
→ 47	The partition method is also explained in detail in the previous section.
→ 64	The swap method simply exchanges the two indicated values.

Open table as spreadsheet

TECHNICAL STAUFF 

Remember the cool Xor technique for exchanging two integer values without the need for a temporary variable? You can improve the performance of your sort ever so slightly by replacing the swap method with this code:

 public static void swap(int i, int j)
 {
 a[i] ^= a[j];
 a[j] ^= a[i];
 a[i] ^= a[j];
 }