begin quoting Mark Schoonover as of Fri, Feb 15, 2008 at 04:44:18PM -0800:
> On Feb 15, 2008 2:43 PM, <[EMAIL PROTECTED]> wrote:
>
> > On Fri, Feb 15, 2008 at 02:13:58PM -0800, Mark Schoonover wrote:
> > > Well, some of my questions were very generic with Lisp. Meaning, how
> > does
> > > that code correspond to what's in the text. My biggest hurdle with Lisp
> > is
> > > program flow. It's not simply top to bottom like Perl is. Even with
> > looping,
> > > Perl still pretty much reads top to bottom. Lisp looks more like a
> > pinball
> > > machine at times, with program flow bouncing around within statements.
> >
> > Yea I know what you mean. For years recursion bugged me. What helped me
> > finally get comfortable with recursion was tail recursiveness. Once I
> > saw that tail recursive code really *is* just like a Perl style loop it
> > seemed
> > less alien to me. YMMV
>
>
> Well, I thought I understood recursion until SICP. I think I understand
> tail recursion too, and essentially it's converting a procedure where the
> last statement is calling itself into an iterative procedure instead of
> recursive. My problem is, I don't always see that in the code, but I know
> it's very important to Lisp. Any recursive procedure, more than likely will
> get written tail recursively. Pretty much if you don't understand this, Lisp
> and SICP will be very difficult to understand.
You can't have tail recursion if you do anything after the recurisve
call. This includes other recursive calls.
> Ok, for example take a look at 1.2.2 Tree Recursion. I've entered the
> recursive procedure for (fib n). I run it with (fib 5), but my output is
> just 5. (I'm using DrScheme) I'm not sure where the 5 even comes from.
> Actually, this particular example is more complicated than it initially
> looks because there's double recursion going on. In the (else (+ (fib (- n
> 1)) (fib (- n 2)))) portion, it looks to me the (- n 2) would never be
> reached because (fib (- n 1)) is always called first, and it'll bail out
> once (= n 1).
That's because you've learned about tail recursion, which isn't
important until you've correctly grasped recursion first.
> Maybe I'm not picturing this correctly in my head, and this could be the
> crux of my problem. Running it through the DrScheme debugger doesn't help
> much either as I watch the little green arrow bounce around like a pinball
> between parens. I guess Larry Wall knew what he was saying when he said lisp
> is like a bowlful of oatmeal with nail clippings in it - or something to
> that effect.
Hopefully yet another visualization might help:
fib(0) = 0
fib(1) = 1
fib(2) = fib(1) + fib(0)
= 1 + 0
= 1
fib(3) = fib(2) + fib(1)
= fib(1) + fib(0) + fib(1)
= 1 + 0 + 1
= 2
fib(4) = fib(3) + fib(2)
= fib(2) + fib(1) + fib(1) + fib(0)
= fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
= 1 + 0 + 1 + 1 + 0
= 3
fib(5) = fib(4) + fib(3)
= fib(3) + fib(2) + fib(2) + fib(1)
= fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1)
= fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1)
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1
= 5
Every call to the fibonacci function results in two recurisve calls,
until you get to fib(1) or fib(0).
It blows up pretty fast. And you'll note that you end up doing the
same work over and over again.
Just wait until you see the Ackermann function.
> This is the other problem I'm having getting my brain around Lisp. It simply
> looks funny! Not funny haha, but funny weird. It almost looks obfuscated. I
> guess I'll get better at it the more I play with it, but for now it leaves
> me scratching my head and mumbling to myself.
How much time do you set aside as a block to do this stuff with lisp?
--
Recursion is nifty but it doeas help
To work it out longhand just to see.
Stewart Stremler
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
