[gclist] tail recursion requires gc

William D Clinger will@ccs.neu.edu
Wed, 07 Aug 1996 14:22:47 +0000


As Rozas, Chase, Baker, O'Keefe, and possibly others have
pointed out, stack allocation often interferes with proper
tail recursion.

You can't reasonably expect an implementation to be properly
tail recursive unless it includes a garbage collector, so
that the compiler can use heap allocation instead of stack
allocation whenever stack allocation would interfere with
tail recursion.

Tail recursion is therefore very tightly coupled to garbage
collection.  General tail recursion optimization _requires_
garbage collection.

So don't expect gcc or any other C compiler to provide fully
general tail recursion any time soon.  That won't happen
until gc becomes a de facto standard part of C.

William Clinger