Question regarding the recursion example from page 51
neilisabass
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.
Purity Control
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.
neilisabass
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.
Phil Rand
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.
--
Phil Rand
phil...@gmail.com
phil...@pobox.com
Peter Frings
> 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.
Hope this helps.
Peter.
Purity Control
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.
neilisabass
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-
Peter Frings
On 16 Apr 2011, at 05:32, neilisabass wrote:
> 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))))
(range 1 10 1) -> (1 2 3 4 5 6 7 8 9 10)
(range 1 10 2) -> (1 3 5 7 9)
(range 999 1 1) -> ()
(don't try this with a negative step value!)
Cheers,
Peter.