*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 lispunrelated stuff for a while)
Newbie questions  and yes, its homework :(

 Posts: 117
 Joined: Tue Aug 10, 2010 11:24 pm
 Location: Calgary, Alberta
 Contact:
Re: Newbie questions  and yes, its homework :(
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:
Do you know C? When you call a function in C do you call it like this?
Or this?
Tail Recursion
In your addtoodd solution, you're using tail recursion.
What is tail recursion  well compare these (the second one is the tail call)
The difference is, in the first example once we call multabit, addsome still needs to add a and 4 to the result. In the second case, once addsome calls multabit, there is nothing left for addsome 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 keepmultiplesof4. Then I'll show you the plain recursive form.
CLUSER> (keepfourstrec '(5 4 5 2 7 8 5 4 57 12 57 16 18) nil)
(4 8 4 12 16)
CLUSER> (keepfoursrec '(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).
CLUSER> (posavgtrec '(0 2 7 5 5 3 1) 0 0)
3
CLUSER> (posavgstart '(0 2 7 5 5 3 1))
3
I was looking at this:
Code: Select all
(defun largestsmallest (lst &optional (small (car lst)) (large (car lst)))
(cond
((null lst) (+ small large))
((< (car lst) small) (largestsmallest (cdr lst) (set 'small (car lst) ) large))
((> (car lst) large) (largestsmallest (cdr lst) small(set 'large (car lst) )))
(t (largestsmallest (cdr lst) small large ))))
Code: Select all
void example(list* l, int small, int big) {
example(l>next, small=l>value, big);
}
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.
}
In your addtoodd solution, you're using tail recursion.
Code: Select all
(defun addtoodd (lst &optional (result (list)))
(cond
((null lst) result)
((evenp (car lst)) (addtoodd (cdr lst) (append result (list(car lst)))))
((oddp (car lst)) (addtoodd (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 multabit (a) (* a 4))
(defun addsome (a) (+ a 4 (multabit a)))
Code: Select all
(defun multabit (a tooadd) (+ (* a 4) tooadd))
(defun addsome (a) (multabit a (+ a 4)))
(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 keepmultiplesof4. Then I'll show you the plain recursive form.
Code: Select all
(defun keepfourstrec (list result)
(cond ((null list) (nreverse result))
((zerop (mod (car list) 4)) (keepfourstrec (cdr list) (cons (car list) result)))
(t (keepfourstrec (cdr list) result))))
(4 8 4 12 16)
Code: Select all
(defun keepfoursrec (list)
(cond ((null list) nil)
((zerop (mod (car list) 4)) (cons (car list) (keepfoursrec (cdr list))))
(t (keepfoursrec (cdr list)))))
(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 posavgtrec (list sum count)
(cond ((null list) (if (zerop count) nil (/ sum count)))
((< (car list) 0) (posavgtrec (cdr list) sum count))
(t (posavgtrec (cdr list) (+ sum (car list)) (1+ count)))))
Code: Select all
(defun posavgrec (list)
(cond ((null list) (values 0 0))
((< (car list) 0) (posavgrec (cdr list)))
(t (multiplevaluebind (sum count) (posavgrec (cdr list))
(values (+ sum (car list)) (1+ count))))))
(defun posavgstart (list)
(multiplevaluebind (sum count) (posavgrec list)
(if (zerop count) nil (/ sum count))))
3
CLUSER> (posavgstart '(0 2 7 5 5 3 1))
3
Need an online wiki database? My Lisp startup http://www.formlis.com combines a wiki with forms and reports.