re: Tail recursion

Do any of the commonly-available compilers for "mainstream" languages
do tail recursion optimization? In particular, any C, c++, or Ada
compilers?


Sun's C and C++ compilers did, 6 years ago, under suitable conditions.
The "under suitable conditions" restriction is a bit of a pain, since
you never really know if you're going to get the optimization, or not.


Suitable conditions are (I think)


1) Parameter area limits
      a) if the recursive call has <= six words of parameters
      b) if the recursive call has no more words of parameters
            than the caller has.


2) Activation record pointer limits
      a) Calling routine cannot also call "setjmp".
      b) Calling routine cannot pass pointers to locals.
      c) Calling routine cannot store pointers to locals in a global.
      d) Calling routine cannot have inline assembly language.
      e) Calling (C++) routine cannot have exception-handling
            (finalizers, destructors to run) associated with the tail
            call.


3) Other....
      a) If the return type of the tail-called routine was a structure,
            there may have been restrictions on the return type of the calling
            routine -- I believe it had to be void return, or same structure.
            This seems "obvious" nowadays, but back in the good old days of
            K&R C and misdeclared routines, one had to be careful not to
            transform a bogus-but-working program into a bogus-but-crashing
            program, where "bogus" means "contains ignorable infractions of
            the recently approved Ansi C standard".


David Chase
chase@naturalbridge.com
[Current versions of gcc turn direct tail recursion into loops quite
consistently, but not indirect. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.