Newbie questions - and yes, its homework :-(

[FKeeL]

*duh* of course. (where I learnt it? dont remember, but google is my friend. The reason I come here is that someone stops me when I begin doing stupid things like this. thanks.)
p
(who now needs to do some lisp-unrelated stuff for a while)

[Warren Wilkinson]

Hey good work FKeel, I was going to mention using functions like 'null' and 'zerop', but you seem to have found them yourself.

I was looking at this:

Code: Select all

(defun largest-smallest (lst &optional (small (car lst)) (large (car lst)))
   (cond
      ((null lst) (+ small large))
      ((< (car lst) small) (largest-smallest (cdr lst) (set 'small (car lst) ) large))
      ((> (car lst) large) (largest-smallest (cdr lst) small(set 'large (car lst) )))
      (t (largest-smallest (cdr lst) small large ))))

Do you know C? When you call a function in C do you call it like this?

Code: Select all

void example(list* l, int small, int big) {
   example(l->next, small=l->value, big); 
}

Or this?

Code: Select all

void example(list* l, int small, int big) {
   example(l->next, l->value, big);           ;; Changed small=l->value to just l->value.
}

Tail Recursion

In your add-to-odd solution, you're using tail recursion.

Code: Select all

(defun add-to-odd (lst &optional  (result (list)))
   (cond
      ((null lst) result)
      ((evenp (car lst)) (add-to-odd (cdr lst) (append result (list(car lst)))))
      ((oddp (car lst)) (add-to-odd (cdr lst) (append result (list (+ 1 (car lst))))))))

What is tail recursion --- well compare these (the second one is the tail call)

Code: Select all

(defun mult-abit  (a) (* a 4))
(defun add-some (a)  (+ a 4 (mult-abit a)))

Code: Select all

(defun mult-abit  (a too-add) (+ (* a 4) too-add))
(defun add-some (a)  (mult-abit a (+ a 4)))

The difference is, in the first example once we call mult-abit, add-some still needs to add a and 4 to the result. In the second case, once add-some calls mult-abit, there is nothing left for add-some to do. This distinction can effect performance in some cases (but this assignment isn't one of those cases, so don't worry).


(I think) every recursive function can be written tail recursively and vis versa. Sometimes the tail recursive way is simpler, sometimes not.

Examples

I don't want to do you're homework for you, so I'll write a tail recursive routine called keep-multiples-of-4. Then I'll show you the plain recursive form.

Code: Select all

(defun keep-fours-trec (list result)
  (cond ((null list) (nreverse result))
	((zerop (mod (car list) 4)) (keep-fours-trec (cdr list) (cons (car list) result)))
	(t (keep-fours-trec (cdr list) result))))

CL-USER> (keep-fours-trec '(5 4 5 2 7 8 5 4 57 12 57 16 18) nil)
(4 8 4 12 16)

Code: Select all

(defun keep-fours-rec (list)
  (cond ((null list) nil)
	((zerop (mod (car list) 4)) (cons (car list) (keep-fours-rec (cdr list))))
	(t (keep-fours-rec (cdr list)))))

CL-USER> (keep-fours-rec '(5 4 5 2 7 8 5 4 57 12 57 16 18))
(4 8 4 12 16)


One More Example

This time I'll show you a tail recursive function that keeps a running sum and count of positive numbers. At the end it gives back the average of those numbers (sum / count).

Code: Select all

(defun pos-avg-trec (list sum count)
  (cond ((null list) (if (zerop count) nil (/ sum count)))
	((< (car list) 0) (pos-avg-trec (cdr list) sum count))
	(t (pos-avg-trec (cdr list) (+ sum (car list)) (1+ count)))))

Code: Select all

(defun pos-avg-rec (list)
  (cond ((null list) (values 0 0))
	((< (car list) 0) (pos-avg-rec (cdr list)))
	(t (multiple-value-bind (sum count) (pos-avg-rec (cdr list))
	     (values (+ sum (car list)) (1+ count))))))

(defun pos-avg-start (list)
  (multiple-value-bind (sum count) (pos-avg-rec list)
    (if (zerop count) nil (/ sum count))))

CL-USER> (pos-avg-trec '(0 2 7 -5 -5 -3 -1) 0 0)
3
CL-USER> (pos-avg-start '(0 2 7 -5 -5 -3 -1))
3