help understanding a simple function

[sycamorex]

This function is from the beginning of Barski's Land of Lisp.

Code: Select all

1.  (defun my-length (list)
2.     (if list
3.          (1+ (my-length (cdr list)))
4.           0))

> (my-length '(list with four objects))
4

I don't think I understand how it works. Could someone kindly correct me.

1. We're defining the function 'my-length' which takes one argument 'list'
2. If the argument exists and is not empty, eg () or nil
3. do the following:
Pass '(with four objects) to the function my-length. It's recursive so then it'll pass '(four objects) to my-length until the list is empty.
What I don't understand here is "(1+" I thought that (1+ n) = (+ n 1). If that's correct, the recursive function adds:
'(list with four objects) + 1
'(with four objects) + 1
'(four objects) + 1
'(objects) + 1
Which doesn't make sense to me. How can you add strings and numbers? I can see that that's probably not the case. That each iteration 1 gets added to make the total of 4 (number of elements) but according to the code it seems to me that it gets added to the list of strings?!

Could you please explain how it really works? Thank you for your time and patience.

[makia]

it's working like this:

(my-length '(list with four objects))
(1+ (my-length '(with four objects)))
(1+ (1+ (my-length '(four objects))))
(1+ (1+ (1+ (my-length '(objects)))))
(1+ (1+ (1+ (1+ (my-length '())))))
(1+ (1+ (1+ (1+ 0))))

p.s. you can (trace my-length) to see something like this

[sycamorex]

Thanks a lot. It seems somewhat clearer to me.
I still can't understand a few things:

That's the output of tracing the function:

Code: Select all

1. Trace: (MY-LENGTH '(LIST WITH FOUR SYMBOLS))                                                           
2. Trace: (MY-LENGTH '(WITH FOUR SYMBOLS))                                                                
3. Trace: (MY-LENGTH '(FOUR SYMBOLS))                                                                     
4. Trace: (MY-LENGTH '(SYMBOLS))                                                                          
5. Trace: (MY-LENGTH 'NIL)                                                                                
5. Trace: MY-LENGTH ==> 0                                                                                 
4. Trace: MY-LENGTH ==> 1                                                                                 
3. Trace: MY-LENGTH ==> 2                                                                                 
2. Trace: MY-LENGTH ==> 3                                                                                 
1. Trace: MY-LENGTH ==> 4  

I still have a problem understanding why it doesn't spit out any errors before the last stage ((1+ (1+ (1+ (1+ 0))))
Before it reaches the last iteration, it seems to be adding numbers and strings (at least that's how I see it)
I know that when it adds, it never reaches the members of the list because first it will call the function recursively.
I understand it is something similar to:

Code: Select all

(1+ (cdr (cdr `(john bill ,1))))  

which, by the way, doesn't work as I don't know how to switch to the code mode before 1. It can't add a number and a non-number element. That's logical and it ignores john and bill before it tries to return anything.

So coming back to the original question: why doesn't it give errors in the my-length function? My attempt of explaining it would be that it doesn't return anything until the final iteration, but
that would probably be wrong because it does return numbers like 2 and 3 before the last call of the function.

Really sorry for lame questions:)
Thank you.

[Paul]

I still have a problem understanding why it doesn't spit out any errors before the last stage ((1+ (1+ (1+ (1+ 0))))
Before it reaches the last iteration, it seems to be adding numbers and strings (at least that's how I see it)

It's not adding numbers and strings. When it calls (1+ (my-length '(with four symbols))), it's adding 1 to whatever (my-length '(with four symbols)) returns. That's not a string, it's a number. It calls (my-length '(four symbols)), which calls (my-length '(symbols)), which calls (my-length '()), which returns 0, so (1+ (my-length '()) == (1+ 0) == 1 is the length of (objects). And (1+ (my-length '(symbols)) == (1+ 1) == 2 is the length of (four symbols), and so on back up the call stack.

(There are no strings involved, anyway: '(list with four symbols) is—as it says—a list of symbols, not strings!)

[sycamorex]

It's not adding numbers and strings. When it calls (1+ (my-length '(with four symbols))), it's adding 1 to whatever (my-length '(with four symbols)) returns. That's not a string, it's a number. It calls (my-length '(four symbols)), which calls (my-length '(symbols)), which calls (my-length '()), which returns 0, so (1+ (my-length '()) == (1+ 0) == 1 is the length of (objects). And (1+ (my-length '(symbols)) == (1+ 1) == 2 is the length of (four symbols), and so on back up the call stack.

(There are no strings involved, anyway: '(list with four symbols) is—as it says—a list of symbols, not strings!)

Thank you. It's getting clearer and clearer, although I can't say I understand it 100%. I'm

Could anyone kindly provide another simple example illustrating the use of recursion (and/or the (1+...) construct)?

Thank you for your patience.

[Philipp]

Well, how about a function adding 1 to each element of a list (assuming it contains only numbers):

Code: Select all

(defun add-1 (lst)
    (if lst
        (cons (1+ (car lst)) (add-1 (cdr lst)))
        nil))

The key point that helped me understand recursion is not to try to follow the recursion.
If you recur on a list, you (well, basically) only have two cases to look at:
- The list you get is empty
If it is, you simply return the 'neutral' or final element to the operation you want to perform: In your first example,
you wanted to sum up numbers, so you pass zero in the end. Here we construct a list from the elements,
so we pass nil at last.
- The list is not empty
Then you perform the operation you want to perform using the value of the application
of your function to the 'cdr of the list. That can get as complicated as you like.
Here, we want to construct a list, so the operation is 'cons. (By the way we use '1+ to add 1 to the current car of the list.)

Try to write a function sum that sums all elements in a list!

[sycamorex]

Thank you for your post.

The key point that helped me understand recursion is not to try to follow the recursion.

Is it possible? LOL. I involuntarily do it which leads me to madness.

Try to write a function sum that sums all elements in a list!

I think it should be as follows:

Code: Select all

(defun sum-of-numbers (lst)                                                                                 
  (if lst                                                                                     
      (+ (car lst) (sum-of-numbers (cdr lst)))                                               
      0))  

[sycamorex]

If hope the sum function above is ok.

Would it be too much if I asked you to give me a couple of tasks that would test my understanding of recursion?
I thought it'd be better if you guys set a task for me, because as I am a LISP newbie, unknowingly I might come up with some tasks that may
require deeper knowledge of LISP and would be to complex for me to implement.


Again, thank you for your time and patience.

[Philipp]

If hope the sum function above is ok.

Very good!

It can be hard to wrap one's mind around some recursive functions,
and since you're learning from Barski (like I did and do) you'll want to have
a feel for it when it comes to 'dice of doom'
If you can afford it and like to improve yourself one little task after another, I'ld highly recomend
the 'little schemer'-book (and it's follower). Despite it's name, you can go through it with CL equally well.

Anyway and though I don't know anything about your general knowledge of CL, here are some tasks for you!

Find the position of an element in a list (you'll want to look at labels for this)!

Code: Select all

(defun pos (elt lst) ...)
> (pos 3 '(0 1 2 3 4)) => 3

Reverse a list (look at append)

Code: Select all

(defun rev (lst) ...)
> (rev '(1 2 3 4)) => (4 3 2 1)

Rewrite sum, so that it calculates the sum of *all* numbers (including sublists)

Code: Select all

(defun sum2 (tree) ...)
> (sum2 '(1 2 (3 (4 5 (6)) 7) 8 9)) => 45

get-till returns the first elements of a list, from element 0 till element 'el':
(Look at nreverse and labels)

Code: Select all

(defun get-till (el lst) ...)
> (get-till 4 '(1 2 3 4 5 6)) => (1 2 3)

You know numberp?
Check if a list contains only numbers (assume it's not empty).

Code: Select all

(defun numbersp (lst) ...)
> (numbersp '(1 2 a)) => nil

Extract the numbers!

Code: Select all

(defun numbers (lst) ...)
> (numbers '(1 2 a b 3 c 4 1)) => (1 2 3 4 1)

Again, thank you for your time and patience.

You're welcome!

[sycamorex]

Excellent. Thank you. I do appreciate it.
Just one question. Do I need to use recursion in each of the tasks?