Artie Gold <firstname.lastname@example.org> 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 <email@example.com>
SGI Network Engineering <http://reality.sgi.com/rpw3/>
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
[Note: firstname.lastname@example.org and email@example.com aren't for humans ]