clisp recursion with two returns

Question

As a new lisp user, I am trying to wrap my head around creating a recursive function. Any advice or resources that can be offered is extremely appreciated!

Algorithm: recursive function that takes a list of integers, and returns a 2 item list, the first value an integer representing the number of odd numbers in the argued list. The second integer represents the number of even numbers in the argued list.

For example: (counterOE '(0 1 2 4 6))

returns: (1 4)

My attempt:

(defun counterOE (L)
(if (equal (length L) 0)
    (return-from counterOE 0))
(if (equal 0 (rem (car L) 2))
    (list (counterEO (cdr L)) (1+ (counterEO (cdr L))))
    (list (1+ (counterEO (cdr L))) (counter EO (cdr L)))))

The obvious error with this function is that it is recursively creating two additional calls every time the function recurses, while you only want one, and that it is creating lists filled with lists, etc. etc. But for the life of me, I cannot figure out how to have 2 (per say) returns with a recursive call in lisp without adding additional sub-functions or additional parameters to the function. Thoughts?

Answer 1

You need to use an accumulator function. This way you can iterate the list while incrementing the two numbers you are interested in returning at the end:

(defun count-split (filter list)
  (labels ((aux (list match no-match)
             (cond ((null list) (values match no-match))
                   ((funcall filter (car list)) (aux (cdr list) (1+ match) no-match))
                   (t (aux (cdr list) match (1+ no-match))))))
    (aux list 0 0)))

Or a guaranteed to not blow stack loop version (but it's not recursive):

(defun count-split (filter list)
  (loop :for i :in list
        :for total :from 0
        :counting (funcall filter i) :into matched
        :finally (return (values matched (- total matched)))))

And both works like this:

(count-split #'oddp '(1 2 3 4 5 6 7 8 9)) ; ==> 5; 4

Answer 2

It is possible to do this without a helper function. What you need to do is to recurse on the rest of the list first, and then modify the result of that according to the first element:

(defun count-odd-even (list)
  (if (endp list)
      '(0 0)
      (destructuring-bind (rest-odd rest-even)
          (count-odd-even (rest list))
        (if (oddp (first list))
            (list (1+ rest-odd) rest-even)
            (list rest-odd (1+ rest-even))))))