Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!cbatt!ihnp4!inuxc!pur-ee!uiucdcs!uiucuxc!uicsrd!harrison
From: harrison@uicsrd.CSRD.UIUC.EDU
Newsgroups: net.lang.lisp
Subject: Re: call/cc and proper tail recursion
Message-ID: <20000008@uicsrd>
Date: Mon, 20-Oct-86 14:17:00 EST
Article-I.D.: uicsrd.20000008
Posted: Mon Oct 20 14:17:00 1986
Date-Received: Sun, 26-Oct-86 01:13:45 EST
References: <20000003@uicsrd>
Lines: 21
Nf-ID: #R:uicsrd:20000003:uicsrd:20000008:000:998
Nf-From: uicsrd.CSRD.UIUC.EDU!harrison    Oct 20 13:17:00 1986


Thanks for replying.

In the TI Scheme Language Reference Manual, p 14, I find:

	Scheme is defined to be properly tail recursive.  This means that
	Scheme handles all tail recursive procedure call with no net growth
	of the stack.

	...its most important characteristic is that it allows recursion
	to subsume iteration completely without losing efficiency.

It seems to me that if tail recursion incurs a penalty of space proportional
to the number of calls, plus time to garbage collect the space, then it is
significantly more expensive than iteration.  I have always assumed that the
'stack' in Scheme is actually maintained as a heap; my confusion came in
reading the claim above (and in several other presentations of Scheme) that
tail-recursive calls occur with no net growth in the stack.  What this seems
to mean in reality is merely that unwinding from a series of tail recursive
calls takes constant time (if we ignore the expense of garbage collecting
all the stack frames allocated).