Tail recursion in C

[Landon Dyer]

(This is partially a response to a posting on su.computers, but I have an
additional question).


Whenever someone asks "why can't I tail-recurse in C?" my eyes bug out, my
vision gets fuzzy, and I basically lose it.  I love tail recursion when I'm
using Scheme, but I'm completely revolted by the concept in C.


Here's what ANSI sez about the semantics of auto scoped variables (section
2.1.2.3 for you language lawyers -- uppercase "italics" are my own):

| An instance of each object with automatic storage duration is associated
| with each entry into its block.  Such an object exists and RETAINS ITS
| LAST-STORED VALUE during the execution of the block and WHILE THE BLOCK IS
| SUSPENDED (BY A CALL OF A FUNCTION or receipt of a signal).


What this means is that you can't tail-recurse if the address of a local can
"leak out" of its scope.  Consider this fragment (sorry about its length):

	--------------------------------
	typedef struct Link {
	    struct Link*  fNext;
	    int           fValue;
	} Link
	
	Link* gLinkList = 0;
	
	void f(int n) {
	    Link elem;
	
	    /* link 'elem' into a global list of 'elem's */
	    elem.fNext = gLinkList;
	    elem.fValue = i;
	    gLinkList = &elem;
	
	    if (n >= 0)
	        f(n-1);		/* recurse */
	    else {
		/* walk 'gLinkList' or something */
	    }
	}
	--------------------------------

At first glance, 'f()' is a tail-recursive function that recurses 'n+1'
times.  But we're in trouble, because third parties (the global 'gLinkList'
in this case) have pointers to locals that are contained in the control
stack.  Fortunately this is something a compiler can detect.

Question: does GCC do this right?


Things get much worse in C++, since destructors for objects have to be
called when the objects go out of scope.  That is, there may be objects to
destroy after the call to 'f(n-1)'.

I would hate to maintain code like that -- especially since the
tail-recursion-ness of a particular function can evaporate the moment
someone adds a constructor / destructor to a class that didn't have one
before.  [C++ has worse problems, but who needs the headache?]


My biggest objection is purely pragmatic.  Your carefully tailored tail-
recursive functions may become real-recursive when you move to a different
compiler.

Now, about that garbage collection....


----
Landon Dyer, Apple Computer, Inc.            "C++ is the FORTH of the 1990s;
Development Systems Group (MPW)               they don't call it 'Uh-oh'
Everything I said here is utter nonsense.     programming for nothing!"