Recursion and Releases

Letters to Cafe Au Lait

This section is for reader comments and questions. To send a "letter to the editor" email it to If you're writing to me about Cafe Au Lait, and don't want your letter published, please tell me. You can also let me know if you'd rather be anonymous. However, if you'd like your email address published with your letter, please tell me. I will not publish your email address without a specific request. And as usual, all letters may be edited for clarity, and brevity; and I reserve the right to decide whether to print a particular letter.

Assignments in if clauses

In the last issue of the Cafe Au Lait newsletter, I wrote that "Java changes much C syntax that's clearly caused problems over the years, for instance allowing assignment statements to appear where one would normally expect a comparison."

Jan Niehusmann, wearing his language lawyer hat, corrected me:

That's not completely true, Java allows assignments in if-clauses. The difference is that Java requires if-clauses to contain boolean values. That is, int a; if( a=1 ) is not allowed, but boolean a; if ( a=true ) is completely legal.

Problems with Third Party Java Implementations

One of the most frequent questions I get runs something like this:

I saw this applet in your book and it works fine in the applet viewer but when I try to run it in Netscape there's a problem.
I received several variations of this question over the last few weeks. The bottom line is this: All current Java implementations including all versions of Netscape have non-trivial bugs. However Sun's Java for Windows 95/NT and for Solaris seems to have the fewest. Before reporting a bug please test it with Sun's Java, preferably for Windows 95/NT or Solaris. If the problem does not occur on those systems, then you've discovered a bug in Cafe, Visual J++, Roaster, Netscape, or whatever environment you're using, not in your code or mine. I cannot help you with a problem with a third party implemenation of Java. If you find a bug in one of these systems (and it's really not hard to do, there are so many bugs to be found) report it to the people who programmed the IDE. There's nothing I can do about it.

Random Fan Mail

I just wanted to congratulate you on your Cafe Au Lait java resources page ... it is excellent! I just subscribed to the newsletter and look forward to reading it. Thanks for all of your efforts.
--Doug Sutherland

Recent Releases

Java continues to move at a rapid pace. Since the first issue of this newsletter, there've been a number of significant new releases.

Sun released a revised specification for remote method invocation (RMI). This spec is supposed to be conformant with the upcoming prebeta release and with the Java 1.1 beta. See Sun also released preliminary information about new features in the AWT 1.1. Most notably there's support for printing and clipboards as well as a completely revamped event model. See I'll write more about these classes in a future issue of Cafe Au Lait.

The ISO has formed a study group for a possible Java standard. The purpose of this Study Group is to coordinate activities during a formal study period leading to possible international standardization of the Java programming language, the Java virtual machine, or alternate programming technologies for World Wide Web applications. To join the mailing list send email to: with the words "subscribe sc22jsg yourname" in the body of the message. I'm participating in the discussions which do not yet appear to be going anywhere. I'll write more about this effort in a future issue.

Netscape released the first beta of their Internet Foundation Classes which will be included in Navigator 4.0. In a stunning display of intelligence and self-interest which one can only hope will be imitated across the industry, they have paid more than lip service to cross-platform issues by simultaneously releasing it for Windows, the Mac, and Unix. I'll write more about these classes in a future issue of Cafe Au Lait.

IBM released Alpha 2a of aglet workbench, a Java intelligent agent system.

Java 1.0.2 for Linux was released after licensing issues were finally straightened out with Sun. It fixes a number of AWT and threading bugs. See

Microsoft released version 1.0 of Visual J++ for $99. The beta received relatively good reviews for a beta product. I haven't yet heard whether the 1.0 version fixed the bugs that were found in the beta, though.

Natural Intelligence has released Roaster DR2.3 for the Mac. It fixes many bugs and supports Java 1.0.2. (finally!) An updater is available from Natural Intelligence's web page.

Dennis Heimbigner of the University of Colorado has released jb3.0a into the public domain. The jb system takes parsers and lexers generated using the Gnu Bison parser and the flex lexer and translates them into Java. Jb is not itself written in Java, but the parsers and lexers that it generates are in Java. As well as bison, flex, and Java, jb requires TCL.

Scott Hudson and Ian Smith of the Graphics, Visualization, and Usability Center at Georgia Institute of Technology have released the first beta of SubArctic, a new Java-based user interface toolkit which offers high level animation support, drag and drop interactions, overlapping, transparent, and composable interface objects, lens interactions, and new debugging support techniques. SubArctic also provides the basic widgets for building traditional, static two-dimensional interfaces including buttons, check-boxes, radio-buttons, scrollbars, labels, menus (including pop-up menus), menubars, icons, image buttons etc. All of the standard components are currently implemented using a Motif-like look-and-feel but this can be changed by the programmer. SubArctic's interactors are implemented entirely in Java and thus do not have the AWT "peer" notion. SubArctic is built on top of AWT and uses AWT for its lowest level functionality such as drawing and input event collection. SubArctic interfaces are "hosted" inside AWT objects such as Applets, Frames, and Canvases and as such may be combined with AWT interfaces. SubArctic uses a totally different event model and composition strategy. SubArctic is free and includes full source code.

ObjectSpace released version 1.1 of theJava Generic Library, a set of container and algorithm classes for Java. Enhancements made since 1.0 include the new algorithms collect, select, reject and inject; non-final Container classes, a new Range class, and improved documentation JGL is free.

Cafe Au Lait hasn't been asleep either. Since the last issue of this newsletter, I've added two completely new areas as well as updating most of the others. The new mailing list page describes over forty different Java related mailing lists and includes automatic subscription forms. Check it out at To add a mailing list that isn't there, just email me a description of the list, the complete subscription and posting information, the URLs of any affiliated web or ftp sites, and the list owner's name and email address. To be eligible for inclusion in my database the list MUST use standard majordomo or listserv commands or the list owner must be willing to manually process subscription requests.

Finally I've started posting corrections to the Java Developer's Resource at The corrections range from the trivial (incorrect font in the s in the word implements on page 46) to the embarrassing (misspelling polymorphism on every page of Chapter 7) to the more serious (Using start() and stop() where I should use suspend() and resume() in Chapter 19). I hope you'll let me know of any more mistakes you find so I can correct them in the second printing. Meanwhile I'll plead mea culpa, and correct the more serious mistakes here as well.



The big change in the preface is that the cafeaulait mailing list has moved. It's now called cal (because the listmaster doesn't like to type long list names) and is available from To subscribe send email to with the line
subscribe cal First_Name Last_Name 
in the body of your message.

Chapter 6: Intro to OOP

Sang Kang of San Diego State University pointed out that I lost track of the cross-references between the problems in Chapter 6 and Chapter 4. Exercise 1 on page 166 should read:

Convert the command line programs of exercises 1, 3, 4, 5, 6, 7, and 8 from chapter 4 into methods that do the calculations but don't handle any input. Then write a main method to handle the input and call the new methods. Do you notice anything similar about the new main methods?

Chapter 17: Windows, Frames, Dialogs and Menus

On page 406 I suggested using the applet's bounds() method to make an educated guess about where to pop up a Frame relative to the monitor. You can do this much more accurately and directly with the getScreenSize() method of java.awt.Toolkit. This returns a Dimension object that tells you how wide and tall the screen is in pixels. For example, here's an applet that centers a Frame on the monitor:

import java.applet.Applet;
import java.awt.Toolkit;
import java.awt.Frame;
import java.awt.Dimension;

public class centerFrame extends Applet {

  public void init() {

    Toolkit tk = Toolkit.getDefaultToolkit();
    Dimension ss = tk.getScreenSize();
    int fwidth = 320;
    int fheight = 240;
    Frame f = new Frame("My Window");
    f.resize(fwidth, fheight);
    f.move((ss.width - fwidth)/2, (ss.height - fheight)/2);;

Chapter 19: Taking Action with Threads

Michael Madrid noticed that in examples 19.9 and 19.10 I stopped the thread when the user clicked the mouse. Rather than stopping and starting the Thread when the user clicks the mouse, I should have suspended and resumed it instead. Furthermore, the applet should have start and stop methods that suspend and resume the thread as well, so it doesn't waste CPU cycles while the user isn't looking at it. You should note that the applet's start and stop methods are completely different from a thread's start and stop methods. By default an applet's start and stop methods do nothing, but a thread's start method calls the thread's run method and a thread's stop method stops the thread from running prematurely. It is not uncommon to call a thread's start or stop method from an applet's start or stop method, but this is not required. Program 19.10 carries the same caveats as Program 19.9; i.e. it should use suspend() and resume() in place of start() and stop(). The applet should also have its own start and stop methods. The revised examples have been placed on Chapter 19's example page at


Today's topic is recursion. I noticed that I gave recursion very little treatment in my book. In fact about all I said was that you could do it. I didn't say anything about how or why you might want to do it. Therefore I'd like to remedy that omission now.

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 withoust 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(); ) {
  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, and I'll report it in the next issue of this newsletter.)

Below is my variation of this benchmark. There are polymorphic 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 = new Date();
   for (int i = 0; i < numpasses; i++) {
      Tak(18.0f, 12.0f, 6.0f);
   Date 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

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 (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.

Subscription Instructions

To subscribe to this newsletter send email to from the account you want to receive mail from with the following text only in the BODY of your message (NOT the subject.)
SUBSCRIBE cal FirstName LastName
You should of course replace FirstName and LastName with your real first name and last name though I won't be particularly bothered if you wish to use an alias.

To unsubscribe from the list send email to from the account you wish to unsubscribe with the following line in the BODY of your message (NOT the subject.)

unsubscribe cal
To get more information on how to use this service, please send the command HELP in a line by itself in a mail message to

You MUST follow these instructions. The list owner will not subscribe or unsubscribe you manually if you do not follow these instructions. Requests to do so will be ignored. Repeated requests will get you dumped in my kill file.

Back Issues

[ Cafe Au Lait | Books | Training | Links | FAQ | Tutorial | User Groups ]

Copyright 1996 Elliotte Rusty Harold
Last Modified October 17, 1996