Recursive Methods
Java supports recursive methods, i.e. even if you’re already inside methodA() you can call methodA(). The easiest way I can think of to explain recursion is to look at a simple acronym, GNU. The GNU project, among other things, is trying to produce free versions of the Unix operating system and many Unix tools, such as lex, yacc, and cc. One minor problem with this effort is that the name Unix is trademarked so the GNU project can’t use it. Hence, instead of Unix, we have GNU, where GNU stands for “Gnu’s Not Unix.” The definition of GNU refers to itself; that is, it’s recursive. So what is GNU? One level deeper it’s “(Gnu’s Not Unix)’s Not Unix.” One level deeper still, it becomes “((Gnu’s Not Unix)’s Not Unix)’s Not Unix.” And so on, ad infinitum. It’s like standing between a pair of mirrors. The images just fade off into the distance with no clear end in sight. In computer programming recursion is achieved by allowing a method to call itself.
You probably already see one problem with recursion. Where does it all end? In fact when you write recursive methods you have to be careful to include stopping conditions. Although Java doesn’t put any particular limits on the depth to which you can expand a recursion, it is very possible to have a run-away recursion eat up all the memory in your computer.
Let’s look at an example. n! (pronounced “En-factorial”) is defined as n times n-1 times n-2 times n-3 … times 2 times 1 where n is a positive integer. 0! is defined as 1. As you see n! = n time (n-1)!. This lends itself to recursive calculation, as in the following method:
public static long factorial (int n) {
if (n == 0) {
return 1;
}
else {
return n*factorial(n-1);
}
}Something to think about: What happens if a negative integer is passed into the factorial method? For example suppose you ask for factorial(-1). Then you get the following chain of calls: -1 * -2 * -3 * -4 * …. If you’re lucky your program may unexpectedly pop into the positive numbers and count down to zero. If you’re not, your program will crash with a StackOutOfMemoryError. Stopping conditions are very important. In this case you should check to see if you’ve been passed a negative integer; and, if you have been, return infinity. (The factorial is a special case of the gamma function for non-negative integers. Although the factorial function is only defined for non-negative integers, the gamma function is defined for all real numbers. It is possible to show that the gamma function is infinite for negative integers.) Java doesn’t support infinite values for longs, though, so return the warning value -1 instead. (Java does support infinite values for floats and doubles.) Here’s a better recursive factorial method:
public static long factorial (int n) {
if (n < 0) {
return -1;
}
else if (n == 0) {
return 1;
}
else {
return n*factorial(n-1);
}
}It can be proven mathematically that all recursive algorithms have non-recursive counterparts. For instance the factorial method could have been written non-recursively like this:
public static long factorial (int n) {
long result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}The non-recursive equivalent in this problem is straight-forward, but sometimes the non-recursive counterpart to a recursive algorithm isn’t at all obvious. To see that one always exists, note that at the machine level of the computer, there’s no such thing as recursion and that everything consists of values on a stack. Therefore even if you can’t find a simpler way to rewrite the algorithm without recursion, you can always use your own stack instead of the Java stack.
Here’s an example of a recursive program for which I have not been able to find a simple, non-recursive equivalent method. The goal is to find all possible RAM configurations for a PC, given the size of the memory chips it will accept and the number of slots it has available. We are not concerned with how the RAM is arranged inside the PC, only with the total quantity of installed RAM. For some computers this can easily be calculated by hand. For instance Apple’s PowerBook 5300 series comes with 8 megabytes of RAM soldered onto the logic board and one empty slot that can hold chips of 8, 16, 32 or 56 MB capacity. Therefore the possible Ram configurations are 8, 16, 24, 40 and 64 MB. However as the number of available slots and the number of available chip sizes increases this becomes a much more difficult problem. The following is a recursive program to calculate and print all possible RAM configurations:
import java.util.Hashtable;
import java.util.Enumeration;
public class RamConfig {
static int[] sizes = {0, 8, 16, 32, 64};
static Hashtable configs = new Hashtable(64);
static int slots[] = new int[4];
public static void main (String args[]) {
System.out.println("Available DIMM sizes are: ");
for (int i=0; i < sizes.length; i++) System.out.println(sizes[i]);
fillSlots(slots.length - 1);
System.out.println("Ram configs are: ");
for (Enumeration e = configs.elements(); e.hasMoreElements(); ) {
System.out.println(e.nextElement());
}
}
private static void fillSlots(int n) {
int total;
for (int i=0; i < sizes.length; i++) {
slots[n] = sizes[i];
if (n == 0) {
total = 0;
for (int j = 0; j < slots.length; j++) {
total += slots[j];
}
configs.put(Integer.toString(total), new Integer(total));
}
else {
fillSlots(n - 1);
}
}
}
}
Recursive methods are also useful for benchmarking. In particular, deep recursion tests the speed with which a language can make method calls. This is important because modern applications have a tendency to spend much of their time calling various API functions. PCWeek uses a benchmark they invented called Tak which performs 63,609 recursive method calls per pass. The algorithm is simple: If y is greater than or equal to x, Tak(x, y, z) is z. This is the nonrecursive stopping condition. Otherwise, if y is less than x, Tak(x, y, z) is Tak(Tak(x-1, y, z), Tak(y-1, z, x), Tak(z-1, x, y)). The Tak benchmark calculates Tak(18, 12, 6) between 100 and 10000 times and reports the number of passes per second. For more information about the Tak benchmark see Peter Coffee’s article, “Tak test stands the test of time” on p. 91 of the 9-30-1996 PCWeek. (The article may be on PCWeek’s web site somewhere, but regrettably that site, while it looks pretty, is lacking some basic navigation aids. I was unable to locate the article, either directly or through their search engine. If anyone finds the URL let me know.)
Below is my variation of this benchmark. There are overloaded integer and floating point versions of the Tak method. Integer is used by default. If the -f flag is given on the command line, the floating point method is used. The number of passes to make may also be entered from the command line. If it is not, 1000 passes are made. The Java Date class is used to time that part of the test where the benchmarking is done.
import java.util.Date;
public class Tak {
public static void main(String[] args) {
boolean useFloat = false;
int numpasses;
for (int i = 0; i < args.length; i++) {
if (args[i].startsWith("-f")) useFloat = true;
}
try {
numpasses = Integer.parseInt(args[args.length-1]);
}
catch (Exception e) {
numpasses = 1000;
}
Date d1, d2;
if (useFloat) {
d1 = new Date();
for (int i = 0; i < numpasses; i++) {
Tak(18.0f, 12.0f, 6.0f);
}
d2 = new Date();
}
else {
d1 = new Date();
for (int i = 0; i < numpasses; i++) {
Tak(18, 12, 6);
}
d2 = new Date();
}
long TimeRequired = d2.getTime() - d1.getTime();
double numseconds = TimeRequired/1000.0;
System.out.println("Completed " + numpasses + " passes in "
+ numseconds + " seconds" );
System.out.println(numpasses/numseconds + " calls per second");
}
public static int Tak(int x, int y, int z) {
if (y >= x) return z;
else return Tak(Tak(x-1, y, z), Tak(y-1, z, x), Tak(z-1, x, y));
}
public static float Tak(float x, float y, float z) {
if (y >= x) return z;
else return Tak(Tak(x-1.0f, y, z), Tak(y-1.0f, z, x), Tak(z-1.0f, x, y));
}
}
If you’d like to try this out right away, you can use the applet interface to the Tak benchmark at http://metalab.unc.edu/javafaq/newsletter/TakApplet.html.
My Powerbook 5300 achieved speeds between 3.5 and 5 passes per second on this test. Sun’s Mac VM was about 10% faster on this test than Natural Intelligence’s. The heavily loaded Sparcstation at metalab.unc.edu (load average 4+) achieved a little more than 3 passes per second. Given the various external factors affecting machine performance, these are hardly scientific measurements. I’d be curious to hear what your results are.
Exercises
- Find the non-recursive equivalent to the Ram Config algorithm.