Subject: Re: processing character entities From: David Carlisle <davidc@xxxxxxxxx> Date: Tue, 27 Jul 1999 22:21:00 +0100 (BST) |
> 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. 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. 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. > In your first version, the recursive call happened _inside_ an expression, that is bad, even though syntactically it looked to be at the end, tail recursion implies structuring things the other way, as in your second version. In a non tail recursive call the lisp engine has to maintain a stack of all the local state of the function, so that it is available when the recursive call returns. In a tail recursive call then the body is typically some sort of if construct, with each branch either not recursing, or being a single recursive call, typically with all the interesting stuff happening in the arguments. Any system dealing with recursion is supposed to `notice' that structure and convert it essentially to a loop, without the overhead of stacking the local state as it can never be used as there is nothing else to do at that level once the recursive call returns. Without tail recursion optimisation you can't really do any looping without hitting some stack limit so it is fairly safe to assume that it happens. Some languages mandate that it happens, I can't remember off hand if dsssl does. David DSSSList info and archive: http://www.mulberrytech.com/dsssl/dssslist
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: processing character entities, Chris Maden | Thread | Re: processing character entities, Daniel Speck |
Re: If statement question, Mitch C. Amiano | Date | refusal to display figures?, Weininger, Nicholas |
Month |