Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite

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.

share|improve this question
 
Why not debug the function using TRACE, STEP or printing the argument? –  Rainer Joswig Oct 1 '12 at 9:38
 
I haven't heard of those functions before actually. I'll have a look at them. –  Bracket Oct 1 '12 at 9:47
 
This book explains the basics: cs.cmu.edu/~dst/LispBook –  Rainer Joswig Oct 1 '12 at 9:56
3  
Thanks- I've realized the bug now, using TRACE. Thank you for the link also. –  Bracket Oct 1 '12 at 10:09
 
that sounds great! –  Rainer Joswig Oct 1 '12 at 10:14
show 2 more comments

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
 
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! –  Joshua Taylor Oct 4 at 19:00
 
I have removed the 'trace' output since I cannot reconcile the meaning of the output with the code. –  Bracket Oct 14 at 14:10
up vote 1 down vote

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))
share|improve this answer
1  
you might be able to use this: (incf (gethash i hash 0)) –  Rainer Joswig Oct 1 '12 at 12:58
 
Thanks, this function contains many new concepts- I'll shorty cover hash tables, so this will be a good example. –  Bracket Oct 2 '12 at 18:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.