Subject: Re: processing character entities From: Brandon Ibach <bibach@xxxxxxxxxxxxxx> Date: Wed, 28 Jul 1999 04:22:43 -0500 |
Quoting DPawson@xxxxxxxxxxx <DPawson@xxxxxxxxxxx>: > A couple of simple examples would be very much > appreciated here David C. > Hi, David P... You may want to check out my "assembler" explanation for Chris. Even if you've never programmed in assembler, it might help clear things up. Now, for a simple example, consider a factorial (n!) function: (define (fact n) (let loop ((c n)) (if (= c 0) 1 (* c (loop (- c 1)))))) This version (which assumes a non-negative integer argument, as does the next version) is not tail-recursive. The reason it isn't tail recursive is because it "does something" with the result of the recursive call. In this case, it multiplies it by "c", and returns the result of the multiplication. You could view the approach taken by this version as "passing up" the results. We recurse all the way down to "c" being equal to 0, then pass the results back up, doing the multiplications as we go. Because we need to remember what the value of "c" was in each level of recursion, we build up a (possibly large) stack of state information. (define (fact n) (let loop ((c n) (r 1)) (if (= c 0) r (loop (- c 1) (* r c))))) This version *is* tail-recursive. When it does the recursive call, it simply returns the result directly, without doing anything more to it. You can view this approach as "passing down". Every time we do a recursive call, we do a multiplication to calculate the "result" argument. Thus, when we get all the way down to "c" being equal to 0, we already know the result. There is no need to "return" to any previous level, so we don't need to save any state information as we go. Thus, no huge stack. In fact, the recursive "call" will end up being more like a "goto". We just bind the new values to the arguments (c and r) and jump back up to the top of the loop. Here's another way to think about the "passing up" vs. "passing down" idea. Imagine you have a handful of pennies that you have to count and stack up. The "passing up" approach would have you take the pennies one by one from the pile in your hand and line them up on a surface. When you were done lining them up, you'd work your way back, counting them as you stack them up, back to the first one you placed on the surface. This could, potentially, require a large surface to hold all the pennies as you line them up. The "passing down" approach would have you simply take the pennies one by one from the pile in your hand, counting and stacking them up as you go. The only surface area you need is the amount taken up by the one penny which is at the bottom of the stack. -Brandon :) DSSSList info and archive: http://www.mulberrytech.com/dsssl/dssslist
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: processing character entities, DPawson | Thread | Tail recursion, was: processing cha, David Carlisle |
Proper tail recursion, Frank A. Christoph | Date | Re: Again with the System Identifie, Joerg Wittenberger |
Month |