Chapter 3

Using Recursion

IN THIS CHAPTER

check Introducing recursion

check Calculating factors with recursion

check Listing directories with recursion

check Sorting with 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 be solved only by recursion, and some problems that can be solved by other techniques are better solved by recursion.

I’m not sure, but I think that 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 doing when they’re struggling with complex recursive programming problems.

True, 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 nonrecursive solution is best. Many problems just cry out for recursion, however.

Calculating 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 that I sound mathematical — is the product of all the integers from 1 to n. Thus the factorial of 5 is 120: 5 × 4 × 3 × 2 × 1.

The nonrecursive solution

You don’t have to use recursion to calculate factorials. Instead, you can use a simple for loop. 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 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.

Factorials get big fast. You should use a long rather than an int to calculate the result. Also, you should use the NumberFormat class to format the result. If int is 20 instead of 5, the preceding 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 nonrecursive 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 preceding section, but it uses recursion to calculate the factorial.

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

Now suppose that you walk up to Jordan and ask, “Jordan, what’s the factorial of 5?”

Jordan says, “I don’t know, but I do know it’s 5 × the factorial of 4. Jeremy, what’s the factorial of 4?”

Jeremy says, “I don’t know, but I do know it’s 4 × the factorial of 3. Jacob, what’s the factorial of 3?”

Jacob says, “I don’t know, but I do know it’s 3 × the factorial of 2. Justin, what’s the factorial of 2?”

Justin says, “I don’t know, but I do know it’s 2 × the factorial of 1. Hey, Bob! What’s the factorial of 1?”

Bob, being the most intelligent of the bunch on account of not having a J-name, replies, “Why, 1, of course.” He tells Justin his answer.

Justin says, “Ah — 2 × 1 is 2.” He tells Jacob his answer.

Jacob says, “Thanks — 3 × 2 is 6.” Jacob tells Jeremy his answer.

Jeremy says, “Dude — 4 × 6 is 24.” Jeremy tells Jordan his answer.

Jordan says, “Very good — 5 × 24 is 120.” He tells you the answer.

That’s pretty much how recursion works.

Displaying Directories

Recursion lends itself well to applications that have to navigate 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 other directories and have no limit in number.

Listing 3-1, at the end of this section, 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.

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

As you can see, I haven’t done Books 6–8 yet. By the time you read this chapter, there will be even more directories to list!

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. (Of course, you can always press Ctrl+C to stop the program, or just close the console window.)

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 can find out much more about this class in the bonus content online. 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 whether 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 the current File object is a directory. If this method returns false, you can assume that the File object is a file.
The getName method returns the name of the file.

Note that Chapter 1 of the bonus content shows how to use the Path class along with an interface called FileVisitor to automatically traverse all the files in a directory tree, including files in any subdirectories. When you use the Path class and the FileVisitor interface, you don't have to write the recursive code yourself.

LISTING 3-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("\nEnter a path: ");

String path = sc.nextLine();→15

File dir = new File(path);→17

if (!dir.exists() || !dir.isDirectory())→18

System.out.println(

"\nThat directory doesn't exist.");

else

{

System.out.println(

"\nListing 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 that 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 wants to list another directory, and the loop repeats if the user answers Y.
→31 This line 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 whether 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. Two spaces are added to the indentation string, however, so that any directories in the f directory are indented two spaces to the right of the current directory.

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.

Earlier in this chapter, I mention 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. Eventually, however, 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, but 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 find out 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. This technique is called Quicksort, and it’s a very ingenious use of recursion. I even show you a simple Java implementation of it.

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 skip the rest of this chapter now.

For most of us, figuring out how sorting algorithms such as Quicksort work is merely an intellectual exercise. The Java API has sorting already built in. (Check out the Arrays.sort method, for example.) 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 thus:

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.
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 called partitioning, and the left and right sides of the arrays are called partitions.
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, which 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. Suppose that 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. The array, however, 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 sorted now. 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.

Using the sort method

In the remainder of this chapter, I present a class that implements the Quicksort algorithm to sort an array of 100 random int values. The array is stored as a static class variable named simply a, so it's visible throughout the class.

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

public static void sort(int startIndex, int endIndex)

{

if (startIndex >= endIndex)

return;

int pivotIndex = partition(startIndex, endIndex);

sort (startIndex, pivotIndex);

sort (pivotIndex+1, endIndex);

}

This method sorts the portion of an array indicated by the starting and ending index values passed to it (startIndex and endIndex). Ignoring the if statement for now, the sort method works by calling a partition method. This method rearranges the array into two 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 again to sort the right partition.

To get the sort method started, you call it with 0 as the starting index value and the array length minus 1 as the ending index value — in other words, the indexes of the first and last element in the array. 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. This is the recursive portion of the algorithm.

The if statement at the beginning of the sort method provides the exit condition that indicates when the recursion should stop. It compares the starting index (startIndex) with the ending index (endIndex). If startIndex is equal to or greater than endIndex, 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. Thus ends the recursion.

Using 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 starting index and ending index that designate the portion of the array that should be sorted. The basic outline of the partition method goes something like this:

Pick a pivot value; for simplicity, use the value of the first element in the partition.
Move all elements that are less than the pivot value to the left side of the partition.
Move all elements that are greater than the pivot value to the right side of the partition.
Return the index of the pivot point.

The most common 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 value. 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 those two array elements.

Note that these two for statements are not nested. The first for statement runs to completion, finding an element that should be swapped on the left side of the array. Then, the second for statement runs to completion, finding an element that should be swapped on the right side of the array. Then the two elements are swapped.

Next, the cycle repeats: 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 that the indexes have crossed and the partitioning is done.

Here’s some code that puts everything together:

public static int partition(int startIndex, int endIndex)

{

int pivotValue = a[startIndex];

int i = startIndex - 1;

int j = endIndex + 1;

while (i < j)

{

for (i++; a[i] < pivotValue; i++);

for (j--; a[j] > pivotValue; j--);

if (i < j)

swap(i, j);

}

return j;

}

Remember that the array being sorted is a static int array named a that’s visible throughout the class, so it isn’t passed into this method as an argument.

The starting and ending index of the partition to be sub-partitioned are passed in as arguments, and the method starts by choosing the first element in the partition to use as the pivot value. For example, if the value of the first element is 42, the partition method will shuffle up the array such that all values that are 42 or less appear on the left side of the array and all values that are greater than 42 are on the right side of the array.

After picking the pivot value, we initialize the index variables i and j from the arguments. Notice that 1 is subtracted from the starting index and 1 is added to the ending index. 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 cross, 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 that 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 3-2 shows a program that gives these methods a workout. This program creates an array of 100 randomly selected numbers with values from 1–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:

76 35 89 96 33 22 72 18 79 14 6 7 31 91 3 58 56 63 77 9

82 31 52 65 14 84 33 47 50 6 1 73 94 63 96 29 12 84 48 85

69 55 4 4 72 80 65 44 82 97 39 42 28 71 96 7 31 3 32 77

78 72 66 4 18 35 27 7 31 67 96 96 30 86 8 98 73 40 55 72

21 98 31 13 87 55 82 42 95 97 15 68 43 70 71 26 32 35 78 99

Sorted array:

1 3 3 4 4 4 6 6 7 7 7 8 9 12 13 14 14 15 18 18

21 22 26 27 28 29 30 31 31 31 31 31 32 32 33 33 35 35 35 39

40 42 42 43 44 47 48 50 52 55 55 55 56 58 63 63 65 65 66 67

68 69 70 71 71 72 72 72 72 73 73 76 77 77 78 78 79 80 82 82

82 84 84 85 86 87 89 91 94 95 96 96 96 96 96 97 97 98 98 99

As you can see, the first array is in random order, but the second array is nicely sorted. (Your results will vary, of course, because the unsorted array will be in a different order every time you run the program as the numbers are generated randomly.)

LISTING 3-2 A Sorting Program

public class QuickSortApp

{

private static int[] a = new int[100];→4

public static void main(String[] args)

{

for (int i = 0; i<a.length; i++)→8

a[i] = (int)(Math.random() * 100) + 1;

System.out.println("Unsorted array:");

printArray();→12

sort(0, a.length - 1);→14

System.out.println("\n\nSorted array:");

printArray();→17

}

private static void printArray()→20

{

System.out.println();

for (int i = 0; i < a.length; i++)

{

if (a[i] < 100)

System.out.print(" ");

if (a[i] < 10)

System.out.print(" ");

System.out.print(a[i] + " ");

if ((i+1) % 20 == 0)

System.out.println();

}

public static void sort(int startIndex, int endIndex)→38

{

if (startIndex >= endIndex)

return;

int pivotIndex = partition(startIndex, endIndex);

sort (startIndex, pivotIndex);

sort (pivotIndex+1, endIndex);

}

public static int partition(int startIndex, int endIndex)→49

{

int pivotValue = a[startIndex];

int i = startIndex - 1;

int j = endIndex + 1;

while (i < j)

{

for (i++; a[i] < pivotValue; i++);

for (j--; a[j] > pivotValue; j--);

if (i < j)

swap(i, j);

}

return j;

}

public static void swap(int i, int j)→66

{

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:

→4 The array is created as a static class variable named a.
→8 This for loop assigns 100 random values to the array.
→12 The printArray method is called to print the unsorted array.
→14 he sort method is called to sort the array.
→17 The printArray method is called again to print the sorted array.
→20 The printArray method uses a for loop to print array elements. Each element is separated by one space. An additional space, however, is printed before each element if the element’s value is less than 100 and yet another space is printed if the value is less than 10. That way, the values line up in columns whether the value is one digit, two digits, or three digits in length. Also, the remainder operator (%) is used to call the println method every 20 elements. Thus this method prints 5 lines with 20 values on each line.
→38 This line declares the sort method, which sorts the partition indicated by the parameters. (The operation of this method is explained in detail in the section “Using the sort method,” earlier in this chapter.)
→49 The partition method is explained in detail in the preceding section.
→66 The swap method simply exchanges the two indicated values.

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];

}