Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!apple!sun-barr!cs.utexas.edu!uunet!mcvax!ukc!etive!aiai!richard
From: richard@aiai.ed.ac.uk (Richard Tobin)
Newsgroups: comp.lang.c
Subject: Re: Tail recursion in C
Message-ID: <570@skye.ed.ac.uk>
Date: 18 Jul 89 18:42:29 GMT
References: <33133@apple.Apple.COM> <10530@smoke.BRL.MIL>
Reply-To: richard@aiai.UUCP (Richard Tobin)
Organization: AIAI, University of Edinburgh, Scotland
Lines: 29

In article <10530@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes:
>In article <33133@apple.Apple.COM> landon@Apple.COM (Landon Dyer) writes:
>>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.
>
>C allows general recursion, not just tail recursion.  

I think the original poster was referring to tail-recursion
optimization, which means turning calls immediately before return into
jumps, thus avoiding stack overflow by re-using the stack frame.  Some
languages (eg Scheme and Postscript) specify this behaviour as part of
the language definition.

To do this in C, the compiler must be sure that there are no pointers
into the stack frame that's about to be re-used.  And if the arguments
are popped of the stack by the caller, you have to make sure it will
still work.  When I last looked at gcc, it generated jumps only for
tail-calls to the same function, and only when the stack frame is empty.

A C compiler that did this more generally would be very useful for
people who want to compile Scheme and other tail-recursive Lisps to C.

-- Richard
-- 
Richard Tobin,                       JANET: R.Tobin@uk.ac.ed             
AI Applications Institute,           ARPA:  R.Tobin%uk.ac.ed@nsfnet-relay.ac.uk
Edinburgh University.                UUCP:  ...!ukc!ed.ac.uk!R.Tobin