XOM API for Processing XML with Java

[Wolfgang Hoschek <whoschek AT lbl.gov>]

> If it is "tail recursion", then
> it usually does not matter.  Optimizers can turn tail recursion (where
> the recursive call is the last instruction in the routine) into
> standard iteration.

"Usually" often does not apply to java compilers. Most java compilers 
won't actually do tail recursion transformations. You can check this 
yourself by running the snippet below. Tail recursion transformation 
would rewrite the recursion into "while (true) {}". If the program 
crashes with a StackOverflow the compiler does not do the optimization; 
if it continues infinitely without any problem the compiler does the 
optimization.

Results:
sun-1.3.x, sun-1.4.x, sun01.5.0beta1 don't do tail recursion 
optimization (both for client and server vm).
Only ibm-1.3.1 and ibm-1.4.1 do it.

public class TailRecursionTest {

  private static int loop(int i) {
    return loop(i);
  }

  public static void main(String[] args) {
    loop(0);
  }
}

Francois Beausoleil wrote:
> On Tue, 10 Feb 2004 12:24:04 -0800, "Wolfgang Hoschek" <whoschek AT lbl.gov>
> said:
> [snip]
>
> > benchmarks years ago is that iteration is always faster than recursion 
> > because it avoids function calls, stack allocations and deallocations, 
>
> [snip]
>
> This depends on the recursive algorithm.  If it is "tail recursion", then
> it usually does not matter.  Optimizers can turn tail recursion (where
> the recursive call is the last instruction in the routine) into standard
> iteration.  For that reason, it is usually better to use tail recursion
> than another recursion type.
>
> I don't have the original code in front of me, so I can't say if it is
> tail recursion.