Re: processing character entities

[Brandon Ibach <bibach@xxxxxxxxxxxxxx>]

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