1

I get a '-Program stack overflow' prompt in clisp when I try to execute the following recursive function that, I believe, returns the most common element in a list:

(defun greater-member (lst)
  (cond  ((null (cdr lst))
                (cons (car lst) (count-if #'(lambda (x) (eql x (car lst))) lst)))
         ((>= (count-if #'(lambda (x) (eql x (car lst))) lst)
              (count-if #'(lambda (x) (eql x (car (remove (car lst) lst)))) lst))
                (greater-member (remove (car (remove (car lst) lst)) lst)))
         (t (greater-member (remove (car lst) lst)))))

e.g greater-number should return as follows:

>(greater-number '(a a a b b b b c))
(b . 4)  

May I ask, what is causing the overflow? I've gotten rid of all the little syntax errors by repeatedly executing greater-number in clisp- the function seems to hold logically.

6
  • Why not debug the function using TRACE, STEP or printing the argument? Commented Oct 1, 2012 at 9:38
  • I haven't heard of those functions before actually. I'll have a look at them. Commented Oct 1, 2012 at 9:47
  • This book explains the basics: cs.cmu.edu/~dst/LispBook Commented Oct 1, 2012 at 9:56
  • 3
    Thanks- I've realized the bug now, using TRACE. Thank you for the link also. Commented Oct 1, 2012 at 10:09
  • (count-if #'(lambda (x) (eql x (car lst))) lst) is (count (car lst) lst) Commented Oct 1, 2012 at 10:37

2 Answers 2

6

I've realized my error now.

Looking at my null test, rather than

(null (cdr lst)) 

I should have

(null (remove (car lst) lst))

So that the redundant, lesser occurring unique elements are removed.

Sign up to request clarification or add additional context in comments.

2 Comments

can you explain how you used trace here (it would complete the answer in a way that will help other users)? Also, since this answered your question, please accept it!
I have removed the 'trace' output since I cannot reconcile the meaning of the output with the code.
1

A little bit more optimized version:

(defun most-common (list)
  (let* ((len 0) (hash (make-hash-table))
         (max-occurences 0)
         key
         (max-possible
          (dolist (i list (ceiling len 2))
            (incf (gethash i hash 0))
            (incf len))))
    (maphash #'(lambda (a b)
                 (if (>= b max-possible)
                     (return-from most-common
                       (if (> b max-occurences) a key))
                     (progn
                       (when (> b max-occurences)
                         (setf key a max-occurences b))
                       (decf max-possible (max 1 (floor b 2))))))
             hash) key))

2 Comments

you might be able to use this: (incf (gethash i hash 0))
Thanks, this function contains many new concepts- I'll shorty cover hash tables, so this will be a good example.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.