Masood Mortazavi's Blog

Recursive Programming in Java

I've done a lot of recursive programming in Java.

I like recursion. That's my weakness. Why? I don't know. Perhaps because I spent a good many years of my life studying logic and methodology of science at Berkeley. There's just a certain beauty to it. So, after many years of logic, when I took a course in LISP, I grew an admiration for it. However, that didn't stop me there. I moved to implement much of CORBA's Relationship Service some 8 years ago in Java, using a lot of recursion. In implementing parts of the POA policy system some 6 years ago here at Sun, I used recursion again.

Here's a snippet of code from Lewis & Chase's book on programming in Java which shows recursion in a mischievous but fun manner in their TowerOfHanoi.java.

   private void moveTower 
   (int numDisks, int start, int end, int temp)
   {
      if (numDisks == 1)
         moveOneDisk (start, end);
      else
      {
         moveTower (numDisks-1, start, temp, end);
         moveOneDisk (start, end);
         moveTower (numDisks-1, temp, end, start);
      }
   }

So, revel in the power of recursion.

It is not always easy to deploy it but when it is, take advantage of it.

Comments

• What do you do about StackOverflowErrors?

  Graham.

  Posted by: grlea on August 03, 2005 at 11:48 PM

• There is one problem.... java hasn't tail-recursion optimisation :(

  If you run something like this:

  
  private int sum(int n) {
  if ( n == 1 ) return 1;
  return n + sum(n-1);
  }

  System.out.println(10000);

  
  you will receive StackOverflowError or OutOfMemoryError :(

  Posted by: splix on August 03, 2005 at 11:52 PM

• If tail recursion isn't optimized by the compiler, tant pis. But
  you can always do it yourself, and leave the recusive version behind
  in the documention (just to give yourself that warm feeling :-)

  public class Test {
  static void moveTower(int numDisks, int start, int end, int temp) {
  for( ; numDisks>0; --numDisks) {
  moveTower(numDisks-1, start, temp, end);
  moveOneDisk(start, end);
  int holder = start;
  start = temp;
  temp = holder;
  }
  }

  static void moveOneDisk(int start, int end) {
  System.out.println(start + " --> " + end);
  }

  public static void main(String[] args) {
  moveTower(5, 0, 2, 1);
  }
  }
  

  Posted by: drlaszlojamf on August 04, 2005 at 05:00 AM

• At university I had a lecturer at university for our Scheme (dialect of LISP) course who always seemed to manage to write *any* program in about ten lines of Scheme. There is some real beauty in its simplicity.

  The StackOverflowErrors are a valid concern, but *only* in situations where the recursion depth is going to be significant. I've written many solutions to problems which are smaller and simplier using recursive techniques.

  Even if it isn't, I often write it first recursively (to understand the problem) and then convert it to (ugly) iterative code to avoice those stack overflows...

  Posted by: archangel on August 04, 2005 at 05:10 AM

• 
  Well-said archangel. Recursion can save volumes. The least it can do is be excellent commentary.

  As computing power (cycles) flatten out and memory grows cheaper, who knows, people may trade time and space differently.

  In any case, we could also give other examples of more efficient uses of recursion, in Java or any other language—for example binary search, which is of Log(N) time complexity. (Example code, using generic types, can be found from the same source.)

  Again, as I noted in my later post, the debate here is really about how particular language machines play time and space complexity against each other, and I don't think there's ever a right answer, theoreticaly speaking—only a right one when we take economics or beauty or some other value as a basis for decision.

  
  

  Posted by: mortazavi on August 04, 2005 at 12:24 PM

• Not to forget the recursive behaviour in XSLT ....

  Posted by: paulbrowne on August 05, 2005 at 12:51 AM

This work is licensed under a Creative Commons License.