Рекурсивная функция переполнения Lisp

Question

Я создаю эвристическую функцию, и она возвращает то, что она должна, но также есть проблема переполнения стека, и я не могу понять, где проблема. Вот код функции я создал:

(defun nextPositions (position) 
    (let*((listaPosAdjacentes) 
     (positionFinal position) 
     (listaFinal NIL)) 
    (setf listaPosAdjacentes (possible-actions2)) 
    (dolist (posAdjacente listaPosAdjacentes) 
     (setf positionFinal position) 
     (setf positionFinal (list (+ (nth 0 positionFinal) (nth 0 posAdjacente)) 
           (+ (nth 1 positionFinal) (nth 1 posAdjacente)))) 
     (push positionFinal listaFinal)) 
    listaFinal)) 

(defun push-unique (element lista) 
    (let ((auxlist lista)) 
    (dolist (i lista) 
     (if (and (equal (nth 0 i) (nth 0 element)) (equal (nth 1 i) (nth 1 element))) 
      (return-from push-unique auxlist))) 

    (push element auxlist) 
    auxlist)) 

(defun recursive (track1 positionslist distance track) 
    (let ((NextValidPositions NIL)) 
    (dolist (position positionslist) 
     (if (equal (track-startpos track) position) 
      (return-from recursive track1) 
     (progn (dolist (i (nextPositions position)) 
       (if (equal (nth (nth 1 i) (nth (nth 0 i) track1)) T) 
        (progn 
         (setf NextValidPositions (push-unique i NextValidPositions)) 
         (setf (nth (nth 1 i) (nth (nth 0 i) track1)) (+ 1 distance)))))))) 
    (recursive track1 NextValidPositions (+ 1 distance) track))) 

(defun compute-heuristic(st) 
    (let* ((track (state-track st)) 
     (distance 0) 
     (track1Final nil) 
     (track1heuristica (track-env track))) 
    (dolist (position (track-endpositions track)) 
     (setf (nth (nth 1 position) (nth (nth 0 position) track1heuristica)) distance)) 
    (setf track1Final (recursive track1heuristica (track-endpositions track) distance track)) 
    (print track1Final) 
    (return-from compute-heuristic track1Final))) 

Результат следующий:

Список возвращает это то, что он должен вернуться, но я не могу понять проблему переполнения стека ,

Код называется так:

(format t "~&Exercise 3.1 - Heuristic~&") 
    (with-open-file (str "out3.1.txt" 
    :direction :input) 
    (format t "~% Solution is correct? ~a~&" (equal (list (compute-heuristic (initial-state *t1*)) (compute-heuristic (make-state :pos '(1 6) :track track)) (compute-heuristic (make-state :pos '(2 8) :track track))) (read str)))) 

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

Любые идеи, что может быть проблемой? Спасибо.

Answer 1

О стиле:

Обычно код не очень хорошо написан, так как он использует слишком много управляющих структур и переменных, которые на самом деле не нужны.

Пример:

(defun push-unique (element lista) 
    (let ((auxlist lista)) 
    (dolist (i lista) 
     (if (and (equal (nth 0 i) 
         (nth 0 element)) 
       (equal (nth 1 i) 
         (nth 1 element))) 
      (return-from push-unique auxlist))) 
    (push element auxlist) 
    auxlist)) 

• ненужными переменная auxlist
• нет необходимости dolist, использовать member
• нет необходимости return-from, просто возвращает значение. Во многих случаях использование return-from является запахом запаха, что указывает на слишком сложный код.
• не push необходимости, просто возвращает результат cons

Better:

(defun push-unique (element list) 
    (if (member element list 
       :test (lambda (a b) 
         (and (equal (first a) (first b)) 
          (equal (second a) (second b))))) 
     list 
     (cons element list))) 

Функциональность существует уже

push-unique функция уже существует в стандартном Common Lisp. Это называется adjoin:

CL-USER 34 > (adjoin 1 '(2 3 4 1 3)) 
(2 3 4 1 3) 

CL-USER 35 > (adjoin 1 '(2 3 4 3)) 
(1 2 3 4 3) 

Просто пройти правильную функцию тестирования для вашей цели ...

(defun push-unique (element list) 
    (adjoin element list 
      :test (lambda (a b) 
        (and (equal (first a) (first b)) 
         (equal (second a) (second b)))))) 

Комментарии & документация

Вероятно, это также хорошая идея, чтобы писать комментарии и документация. В противном случае нужно угадать/указать, какова цель этих функций.