Recursion and Releases

Letters to Cafe Au Lait

Assignments in if clauses

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

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.

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.

Recent 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 http://chatsubo.javasoft.com/current/. 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 http://www.javasoft.com/products/JDK/1.1/designspecs/awt/index.html. 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: sc22jsg-request@dkuug.dk 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 http://java.blackdown.org/java-linux/Information.html

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 http://sunsite.unc.edu/javafaq/mailinglists.html. 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 http://sunsite.unc.edu/javafaq/corrections/ 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.

Corrections

Preface

subscribe cal First_Name Last_Name 

Chapter 6: Intro to OOP

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

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);
    f.show();
    
  }
  
}

Chapter 19: Taking Action with Threads

Recursion

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);
  }

}

public static long factorial (int n) {

  if (n < 0) {
    return -1;
  } 
  else if (n == 0) {
    return 1;
  }
  else {
    return n*factorial(n-1);
  }

}

public static long factorial (int n) {

  long result = 1;
  
  for (int i = 1; i <= n; i++) {
    result *= i;
  }
  
  return result;

}

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);
       }
    }      
  
  }
  
}

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));   
  
  }

}

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

Subscription Instructions

SUBSCRIBE cal FirstName LastName

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

unsubscribe cal

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.