Skip to Content.
Sympa Menu

xom-interest - Re: [XOM-interest] Three cosmetic patches

xom-interest AT lists.ibiblio.org

Subject: XOM API for Processing XML with Java

List archive

Chronological Thread  
  • From: Wolfgang Hoschek <whoschek AT lbl.gov>
  • To: xom-interest AT lists.ibiblio.org
  • Cc:
  • Subject: Re: [XOM-interest] Three cosmetic patches
  • Date: Wed, 11 Feb 2004 10:24:31 -0800

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






Archive powered by MHonArc 2.6.24.

Top of Page