Subject: Re: lambda mysticism?
From: (Rob Warnock)
Date: 6 Sep 2001 09:42:06 GMT
Newsgroups: comp.lang.scheme
Message-ID: <9n7gde$h1hbf$>
Artie Gold  <> wrote:
| Raistlin wrote:
| > What is tail recursion, compared to normal recursion that I see in C?
| Whenever the last thing a function does is call itself, therefore
| meaning that all of its variables, i.e. the arguments themselves and any
| locals are no longer needed it may be transformed into a loop -- meaning
| that the needed stack space is O(1) as opposed to O(n). Scheme
| guarantees that such code is optimized appropriately.

But even further, Scheme requires that *all* tail-position calls be so
optimized, not just calls to the same function. That is, the following
code should run forever without running out of memory:

	(define (a) (if (random-bool) (b) (c))
	(define (b) (if (random-bool) (c) (a))
	(define (c) (if (random-bool) (a) (b))

This is *very* handy for coding state-machines...


Rob Warnock, 30-3-510		<>
SGI Network Engineering		<>
1600 Amphitheatre Pkwy.		Phone: 650-933-1673
Mountain View, CA  94043	PP-ASEL-IA

[Note: and aren't for humans ]