I am rather embarrassed that I cant figure out how the recursion
example works on page 51.
It seems far to important for me to glaze over. I would love an
explicit step by step of what lisp is doing.
It helps if you work through the function with the simplest case and
then work up to more complex examples.
if is asking a true or false question, false is triggered on the null
or empty list.
so for an empty list 0 is returned. which is what you would expect.
for any non empty list
(1+ (my-length (cdr list))) is returned
the cdr of the list is everything bar the first item in the list.
so for a list of 1 item it is saying add the to the result of the
function my-length to the rest of the list (for a 1 item list the rest
of the list is empty) you know the function my-length returns 0 for an
empty list so it calculates 1 + 0 or in lisp (+ 1 0)
the same happens for a 2 item list but with an extra recursion in
my-length says add 1 to the result of my length for the rest of the
list (ie a 1 item list)
you can see what happens when it calculates a 1 item list from the
preceding paragraph.
This is called natural recursion because you are always repeating a
function call on a version of the list that is getting smaller, ie you
are lopping the first item off the list (the car of the list) and
returning the rest to the function to get 1 step nearer to the
solution.
On Apr 14, 4:49 am, neilisabass <neilisab...@gmail.com> wrote:
> I am rather embarrassed that I cant figure out how the recursion
> example works on page 51.
> It seems far to important for me to glaze over. I would love an
> explicit step by step of what lisp is doing.
Thank you, Purity Control, for taking the time to answer me in such
detail.
I am really struggling with the order of operation and how the
functions pass data to and fro.
I understand that (if list ; evaluates for T / 'nil
I understand that if I (cdr '(list with four symbols) it returns (WITH
FOUR SYMBOLS) I assume that it returns (WITH FOUR SYMBOLS) to the
function that called it.
I assume that the function that called (cdr list) is my-length but I
simply can not understand what happens next or when (+ 1 0) occurs.
I am sure that your paragraph explains this, but I have been reading
it all day and simply can't map it out in my head (or on paper).
I do appreciate you taking the time to try to explain it to me, and
apologize that I don't comprehend what is probably very obvious.
Hopefully it will become clearer with time.
On Apr 14, 1:55 am, Purity Control <cr...@craigferry.net> wrote:
> It helps if you work through the function with the simplest case and
> then work up to more complex examples.
> if is asking a true or false question, false is triggered on the null
> or empty list.
> so for an empty list 0 is returned. which is what you would expect.
> for any non empty list
> (1+ (my-length (cdr list))) is returned
> the cdr of the list is everything bar the first item in the list.
> so for a list of 1 item it is saying add the to the result of the
> function my-length to the rest of the list (for a 1 item list the rest
> of the list is empty) you know the function my-length returns 0 for an
> empty list so it calculates 1 + 0 or in lisp (+ 1 0)
> the same happens for a 2 item list but with an extra recursion in
> my-length says add 1 to the result of my length for the rest of the
> list (ie a 1 item list)
> you can see what happens when it calculates a 1 item list from the
> preceding paragraph.
> This is called natural recursion because you are always repeating a
> function call on a version of the list that is getting smaller, ie you
> are lopping the first item off the list (the car of the list) and
> returning the rest to the function to get 1 step nearer to the
> solution.
> On Apr 14, 4:49 am, neilisabass <neilisab...@gmail.com> wrote:
> > Hello all,
> > I am rather embarrassed that I cant figure out how the recursion
> > example works on page 51.
> > It seems far to important for me to glaze over. I would love an
> > explicit step by step of what lisp is doing.
Sometimes it helps me to think about function and expression evaluation in lisp not like machinery (put in the raw materials, turn the crank, and out comes the answer), but like simple substitutions in math. So when an expression containing (+ 3 5) is evaluated, think of it as erasing the (+ 3 5) and substituting 8.
The same principal applies in a recursive function call. The recursive call substitutes a simpler version of the problem, and this continues until you're only left with the simplest case.
When I first learned about recursion, it seemed like cheating, or using magic. I would get all tangled up trying to picture arguments being pushed onto the stack, being popped off, and so on. Eventually, instead of suddenly seeing how it all worked in a blinding flash, I just quit worrying about how the language implemented it, and trusted that the language implementers were much better engineers than I. Maybe I've reached enlightenment. Anyway, I now let the language implementers worry about how it works internally, and concentrate on making sure my recursive calls are dealing with a simpler piece of the problem at each step.
I hope this helps, but don't feel too bad if it doesn't. If learning this stuff weren't a little mind-bending, it wouldn't be near as much fun.
On Thu, Apr 14, 2011 at 6:37 PM, neilisabass <neilisab...@gmail.com> wrote: > Thank you, Purity Control, for taking the time to answer me in such > detail.
> I am really struggling with the order of operation and how the > functions pass data to and fro. > I understand that (if list ; evaluates for T / 'nil > I understand that if I (cdr '(list with four symbols) it returns (WITH > FOUR SYMBOLS) I assume that it returns (WITH FOUR SYMBOLS) to the > function that called it. > I assume that the function that called (cdr list) is my-length but I > simply can not understand what happens next or when (+ 1 0) occurs.
> I am sure that your paragraph explains this, but I have been reading > it all day and simply can't map it out in my head (or on paper). > I do appreciate you taking the time to try to explain it to me, and > apologize that I don't comprehend what is probably very obvious. > Hopefully it will become clearer with time.
> On Apr 14, 1:55 am, Purity Control <cr...@craigferry.net> wrote: >> It helps if you work through the function with the simplest case and >> then work up to more complex examples.
>> if is asking a true or false question, false is triggered on the null >> or empty list. >> so for an empty list 0 is returned. which is what you would expect.
>> for any non empty list >> (1+ (my-length (cdr list))) is returned
>> the cdr of the list is everything bar the first item in the list. >> so for a list of 1 item it is saying add the to the result of the >> function my-length to the rest of the list (for a 1 item list the rest >> of the list is empty) you know the function my-length returns 0 for an >> empty list so it calculates 1 + 0 or in lisp (+ 1 0)
>> the same happens for a 2 item list but with an extra recursion in >> my-length says add 1 to the result of my length for the rest of the >> list (ie a 1 item list) >> you can see what happens when it calculates a 1 item list from the >> preceding paragraph.
>> This is called natural recursion because you are always repeating a >> function call on a version of the list that is getting smaller, ie you >> are lopping the first item off the list (the car of the list) and >> returning the rest to the function to get 1 step nearer to the >> solution.
>> On Apr 14, 4:49 am, neilisabass <neilisab...@gmail.com> wrote:
>> > Hello all,
>> > I am rather embarrassed that I cant figure out how the recursion >> > example works on page 51. >> > It seems far to important for me to glaze over. I would love an >> > explicit step by step of what lisp is doing.
>> > Thanks in advance.
-- Phil Rand philr...@gmail.com philr...@pobox.com
On Thu, Apr 14, 2011 at 5:49 AM, neilisabass <neilisab...@gmail.com> wrote: > I am rather embarrassed that I cant figure out how the recursion > example works on page 51. > It seems far to important for me to glaze over. I would love an > explicit step by step of what lisp is doing.
The key in understanding recursion is ‘wishful thinking’. Or as Phil Rand said: 'quit worrying' :-)
When you're *writing* the my-length function, just trust that calling my-length will do what it's supposed to do: return the length of a list. Nothing more, nothing less. It's just a function. The fact that you're still writing that function doesn't matter: once you've finished writing it it will just work.
The ‘algorithm’ of my-length is quite simple: tally up 1 for the first element, then add the length of the rest of the list: (1+ (my-length (cdr lst))) <- trust my-length will work and return you the length.
Of course, the length of an empty list is 0 (by definition)
So, the entire function simply checks whether the list is empty, in which case it returns 0. If the list is not empty, it calls this fantastic function my-length to calculate the length of the rest of the list and adds 1 to it.
As Phil said, subsitution may also help: (my-length '()) is 0. So (my-length '(d)) does 1 + (my-length '()), which is 1 + 0 = 1. And (my-length '(a b c d)) does 1 + (my-length '(b c d)), which is 1 + 3 = 4.
Just believe my-length does what it's supposed to do and quit worrying.
Do not get disheartened. It is a very different way of thinking
compared to say a c based language and will take some time to bed in.
The land of lisp is one of the best books i have read on lisp but it
goes at quite a pace so you are right to stop and make sure you
understand before going any further.
If you think of lisp expressions as ordering in the same way as
complex mathematic expressions this may help you. Whatever a function
returns sits where the function call is.
(defun my-length (list)
(if list
(1+ (my-length (cdr list)))
0))
> (my-length ' (list with four symbols))
becomes
(if '(list with four variables)
which evaluate to true so we operate on the line
(1+ (my-length (cdr list)))
which becomes
(1+ (my-length '(with four varianbles)))
so we get to
(1+ (if '(with four variables)......))
which again evaluates to true so we take the first line
(1+ (1+ (my-length '(four variables))))
which becomes
(1+ (1+ (if '(four variables).....)))
again true so
(1+ (1+ (1+ (my-length '(variables)))))
which becomes
(1+ (1+ (1+ (if ('variables) ....))))
which again avaluates to true so
(1+ (1+ (1+ (1+ (my-length '())))))
which becomes
(1+ (1+ (1+ (1+ (if '() .....)))))
this evaluates to false and so returns the second line which is zero
(1+ (1+ (1+ (1+ 0))))
(1+ (1+ (1+ 1)))
(1+ (1+ 2))
(1+ 3)
4
Hope this makes a bit more sense. If i haven't explained in a way that
makes sense for you then do repost. It is well worth grappling with
because once the light finally goes on it will open up a different way
of thinking about programs to you.
On Apr 15, 2:37 am, neilisabass <neilisab...@gmail.com> wrote:
> Thank you, Purity Control, for taking the time to answer me in such
> detail.
> I am really struggling with the order of operation and how the
> functions pass data to and fro.
> I understand that (if list ; evaluates for T / 'nil
> I understand that if I (cdr '(list with four symbols) it returns (WITH
> FOUR SYMBOLS) I assume that it returns (WITH FOUR SYMBOLS) to the
> function that called it.
> I assume that the function that called (cdr list) is my-length but I
> simply can not understand what happens next or when (+ 1 0) occurs.
> I am sure that your paragraph explains this, but I have been reading
> it all day and simply can't map it out in my head (or on paper).
> I do appreciate you taking the time to try to explain it to me, and
> apologize that I don't comprehend what is probably very obvious.
> Hopefully it will become clearer with time.
> On Apr 14, 1:55 am, Purity Control <cr...@craigferry.net> wrote:
> > It helps if you work through the function with the simplest case and
> > then work up to more complex examples.
> > if is asking a true or false question, false is triggered on the null
> > or empty list.
> > so for an empty list 0 is returned. which is what you would expect.
> > for any non empty list
> > (1+ (my-length (cdr list))) is returned
> > the cdr of the list is everything bar the first item in the list.
> > so for a list of 1 item it is saying add the to the result of the
> > function my-length to the rest of the list (for a 1 item list the rest
> > of the list is empty) you know the function my-length returns 0 for an
> > empty list so it calculates 1 + 0 or in lisp (+ 1 0)
> > the same happens for a 2 item list but with an extra recursion in
> > my-length says add 1 to the result of my length for the rest of the
> > list (ie a 1 item list)
> > you can see what happens when it calculates a 1 item list from the
> > preceding paragraph.
> > This is called natural recursion because you are always repeating a
> > function call on a version of the list that is getting smaller, ie you
> > are lopping the first item off the list (the car of the list) and
> > returning the rest to the function to get 1 step nearer to the
> > solution.
> > On Apr 14, 4:49 am, neilisabass <neilisab...@gmail.com> wrote:
> > > Hello all,
> > > I am rather embarrassed that I cant figure out how the recursion
> > > example works on page 51.
> > > It seems far to important for me to glaze over. I would love an
> > > explicit step by step of what lisp is doing.
Wow. Thank you all for replying; it is very generous of you all to
tutor me like this. I do understand now how these 5 lines of
tremendous code work. I am very happy to get that worked out.
Purity Control, This explicit explanation is exactly what I needed.
Thank you for taking the time to type that out.
-Much obliged-
On Apr 15, 2:47 am, Purity Control <cr...@craigferry.net> wrote:
> Do not get disheartened. It is a very different way of thinking
> compared to say a c based language and will take some time to bed in.
> The land of lisp is one of the best books i have read on lisp but it
> goes at quite a pace so you are right to stop and make sure you
> understand before going any further.
> If you think of lisp expressions as ordering in the same way as
> complex mathematic expressions this may help you. Whatever a function
> returns sits where the function call is.
> becomes
> (if '(list with four variables)
> which evaluate to true so we operate on the line
> (1+ (my-length (cdr list)))
> which becomes
> (1+ (my-length '(with four varianbles)))
> so we get to
> (1+ (if '(with four variables)......))
> which again evaluates to true so we take the first line
> (1+ (1+ (my-length '(four variables))))
> which becomes
> (1+ (1+ (if '(four variables).....)))
> again true so
> (1+ (1+ (1+ (my-length '(variables)))))
> which becomes
> (1+ (1+ (1+ (if ('variables) ....))))
> which again avaluates to true so
> (1+ (1+ (1+ (1+ (my-length '())))))
> which becomes
> (1+ (1+ (1+ (1+ (if '() .....)))))
> this evaluates to false and so returns the second line which is zero
> (1+ (1+ (1+ (1+ 0))))
> (1+ (1+ (1+ 1)))
> (1+ (1+ 2))
> (1+ 3)
> 4
> Hope this makes a bit more sense. If i haven't explained in a way that
> makes sense for you then do repost. It is well worth grappling with
> because once the light finally goes on it will open up a different way
> of thinking about programs to you.
> On Apr 15, 2:37 am, neilisabass <neilisab...@gmail.com> wrote:
> > Thank you, Purity Control, for taking the time to answer me in such
> > detail.
> > I am really struggling with the order of operation and how the
> > functions pass data to and fro.
> > I understand that (if list ; evaluates for T / 'nil
> > I understand that if I (cdr '(list with four symbols) it returns (WITH
> > FOUR SYMBOLS) I assume that it returns (WITH FOUR SYMBOLS) to the
> > function that called it.
> > I assume that the function that called (cdr list) is my-length but I
> > simply can not understand what happens next or when (+ 1 0) occurs.
> > I am sure that your paragraph explains this, but I have been reading
> > it all day and simply can't map it out in my head (or on paper).
> > I do appreciate you taking the time to try to explain it to me, and
> > apologize that I don't comprehend what is probably very obvious.
> > Hopefully it will become clearer with time.
> > On Apr 14, 1:55 am, Purity Control <cr...@craigferry.net> wrote:
> > > It helps if you work through the function with the simplest case and
> > > then work up to more complex examples.
> > > if is asking a true or false question, false is triggered on the null
> > > or empty list.
> > > so for an empty list 0 is returned. which is what you would expect.
> > > for any non empty list
> > > (1+ (my-length (cdr list))) is returned
> > > the cdr of the list is everything bar the first item in the list.
> > > so for a list of 1 item it is saying add the to the result of the
> > > function my-length to the rest of the list (for a 1 item list the rest
> > > of the list is empty) you know the function my-length returns 0 for an
> > > empty list so it calculates 1 + 0 or in lisp (+ 1 0)
> > > the same happens for a 2 item list but with an extra recursion in
> > > my-length says add 1 to the result of my length for the rest of the
> > > list (ie a 1 item list)
> > > you can see what happens when it calculates a 1 item list from the
> > > preceding paragraph.
> > > This is called natural recursion because you are always repeating a
> > > function call on a version of the list that is getting smaller, ie you
> > > are lopping the first item off the list (the car of the list) and
> > > returning the rest to the function to get 1 step nearer to the
> > > solution.
> > > > I am rather embarrassed that I cant figure out how the recursion
> > > > example works on page 51.
> > > > It seems far to important for me to glaze over. I would love an
> > > > explicit step by step of what lisp is doing.
> Wow. Thank you all for replying; it is very generous of you all to > tutor me like this. I do understand now how these 5 lines of > tremendous code work. I am very happy to get that worked out. > Purity Control, This explicit explanation is exactly what I needed. > Thank you for taking the time to type that out.
I'm glad you understand how the runtime handles the recursion. You'll probably have to do the same exercise when LoL discusses tail recursion on p331.
But this was a very simple example; it will be very hard to depict or write down these explicit steps when you get to the more advanced recursive functions in later chapters. You'll get lost very rapidly when you try to understand such a function by expanding it.
Try to understand a recursive function without having to write out the steps, you'll save yourself a lot of trouble.
Here's one for the road :-)
(defun range (min max step) (if (> min max) (list) (cons min (range (+ min step) max step))))
