Basic LISP recursion, enumerate values greater than 3

Question

I need a recursive LISP function that enumerates the number of elements in any list of numbers > 3. I'm not allowed to use lets, loops or whiles and can only use basic CAR, CDR, SETQ, COND, CONS, APPEND, PROGN, LIST...

This is my attempt at the function:

(defun foo (lst) 
  (COND ((null lst) lst) 
    (T (IF (> (CAR lst) 3) 
      (1+ (foo (CDR lst)))
      (foo (CDR lst)) ) ) ) )

The function call:

(foo '(0 1 2 3 4 5 6))

Answer 1

Your code is pretty close to correct, just a small mistake in the base case:

For the empty list you return the empty list. So if you have the list (6), you add 6 to foo of the empty list, which is the empty list. That does not work because you can't add a number to a list.

You can easily fix it by making foo return 0 instead of lst when lst is empty.

As a style note: Mixing cond and if like this, seems a bit redundant. I would write it like this, using only cond instead:

(defun foo (lst) 
  (cond
    ((null lst)
      0)
    ((> (car lst) 3) 
      (1+ (foo (cdr lst))))
    (T
      (foo (cdr lst)))))

Answer 2

Some stylistic points:

• There's no need to put some Lisp built-ins in uppercase. It's not 1958 anymore!
• But if you are going to put built-ins in uppercase, why not DEFUN and NULL?
• You have an if inside the last branch of your cond. This is redundant. Since the purpose of cond is testing conditions, why not use it?
• There's no need to space out your closing parentheses like that. No-one counts parentheses these days, we have parenthesis-matching editors.
• Lisp has separate namespaces for functions and values, so you don't have to call your argument lst to avoid conflicting with the built-in function list.

If you were programming this for real, of course you'd use count-if:

(count-if #'(lambda (x) (> x 3)) '(0 1 2 3 4 5 6))
    ==> 3

Answer 3

One save you can have on duplication of the recursive call:

(defun foo (l)
  (if (null l) 0               ; if list is empty, return 0
    (+ (if (> (car l) 3) 1 0)  ; else +1 if condition is satisfactory
      (foo (cdr l)))))         ; plus the result from the rest