Artie Gold  <agold@bga.com> 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))
	(a)

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


-Rob

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

[Note: aaanalyst@sgi.com and zedwatch@sgi.com aren't for humans ]