переполнение стека при выполнении рекурсивной функции lisp

Я получаю приглашение «-Program stack overflow» в clisp, когда пытаюсь выполнить следующую рекурсивную функцию, которая, как мне кажется, возвращает наиболее распространенный элемент в списке:

(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)))))

например, большее число должно возвращаться следующим образом:

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

Могу я спросить, что вызывает переполнение? Я избавился от всех небольших синтаксических ошибок, повторно выполнив большее число в clisp — кажется, что функция выполняется логически.


recursion stack-overflow lisp common-lisp clisp
person category    schedule 01.10.2012    source источник
comment
Почему бы не отладить функцию, используя TRACE, STEP или вывод аргумента?   -  person Rainer Joswig    schedule 01.10.2012
comment
На самом деле я не слышал об этих функциях раньше. Я посмотрю на них.   -  person category    schedule 01.10.2012
comment
В этой книге объясняются основы: cs.cmu.edu/~dst/LispBook   -  person Rainer Joswig    schedule 01.10.2012
comment
Спасибо! Теперь я понял ошибку, используя TRACE. Спасибо и за ссылку.   -  person category    schedule 01.10.2012
comment
(count-if #'(лямбда (x) (eql x (car lst))) lst) is (count (car lst) lst)   -  person Rainer Joswig    schedule 01.10.2012
comment
Спасибо за это - я не знал о существовании графа.   -  person category    schedule 02.10.2012

Ответы (2)


arrow_upward
6
arrow_downward

Я понял свою ошибку сейчас.

Глядя на мой тест null, а не

(null (cdr lst))

мне следует иметь

(null (remove (car lst) lst))

Так что избыточные, менее встречающиеся уникальные элементы удаляются.

person category    schedule 01.10.2012
comment
можете ли вы объяснить, как вы использовали trace здесь (это дополнит ответ таким образом, что это поможет другим пользователям)? Кроме того, поскольку это ответило на ваш вопрос, пожалуйста, примите его! - person Joshua Taylor; 04.10.2013
comment
Я удалил вывод «трассировки», так как не могу согласовать значение вывода с кодом. - person category; 14.10.2013

arrow_upward
1
arrow_downward

Немного более оптимизированная версия:

(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))
person Community    schedule 01.10.2012
comment
вы могли бы использовать это: (incf (gethash i hash 0)) - person Rainer Joswig; 01.10.2012
comment
Спасибо, эта функция содержит много новых концепций — я кратко расскажу о хеш-таблицах, так что это будет хороший пример. - person category; 02.10.2012