Subject: Re: processing character entities From: Daniel Speck <dspeck@xxxxxxx> Date: Tue, 27 Jul 1999 17:35:16 -0400 |
Chris Maden wrote: > I do not understand this whole tail-recursion thing. I'll give it a shot. A recursive function is one that (directly or indirectly) calls itself. A tail-recursive function is a recursive function that only calls itself as the last thing it does. > > > I *thought* I did, but Brandon's post indicates otherwise. I had a > loop of the form: > > (let loop > ((init value)) > (if loop-is-done > null-object > (append-objects this-one > (loop change-value)))) This is not tail-recursive because (append-objects ...) must wait for the recursive call to loop to finish before it can be called. This builds up data on the stack. > > > I thought the key feature of tail recursion was that the recursive > call was the last thing in the loop. In fact, I've been pretty > careful to write most or all of my loops with this form. However, > Brandon suggests a loop of the form: > > (let loop > ((init value) > (result empty-object) > (if loop-is-done > result > (loop change-value > (append-objects result > this-one))))) > > So what, exactly, is the defining feature of tail recursion? It seems > to me that the second form involves passing a larger and larger result > object into the recursion, possibly with a new copy each time. The alternative that you provide builds up the result implicitly on the stack instead of explicitly in a parameter. The size of the result isn't important (both solutions eventually need to return the same result) the way the result is constructed is what matters. > Now, I > can see how that won't happen if the loop's execution is optimized, > but I am really an assembly programmer in disguise, and don't like to > assume magical optimization by some other entity. Scheme and DSSSL are guaranteed to be properly tail-recursive, i.e., they treat tail-recursive calls as jumps not procedure calls. > If someone can > assure me that this is, indeed, The Lisp Way (preferably with an > explanation of why), I'll deal with it, but I'd like to understand > what's going on before I re-write a whole lot of code. This is indeed the Scheme/DSSSL way. -dan -- Daniel Speck Bureau of National Affairs, Inc. Voice: +1 202.452.6596 1231 25th Street, NW Fax: +1 202.331.5178 Washington, DC 20037 e-mail: dspeck@xxxxxxx DSSSList info and archive: http://www.mulberrytech.com/dsssl/dssslist
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: processing character entities, David Carlisle | Thread | Re: processing character entities, Brandon Ibach |
refusal to display figures?, Weininger, Nicholas | Date | Re: processing character entities, Russell Steven Shawn |
Month |