Common Lisp: использование (let) для вычисления рекурсивной функции

Поэтому я написал что-то, что возвращает максимальную сумму подмножества, учитывая список положительных целых чисел. Однако я хотел бы использовать (let), чтобы сделать код более эффективным. Я хотел бы знать, если и как это возможно.

(defun subset-sum1 (numbers capacity)
  (subset-sum numbers capacity 0))

(defun subset-sum (numbers capacity counter) 
  (cond ((null numbers) counter)
        ((= counter capacity) counter) ;; return if counter 'hits' the capacity
        ((< capacity (+ (car numbers) counter))
         (subset-sum (cdr numbers) capacity counter)) ;; cdr if car branch exceeds capacity
        ((<= (subset-sum (cdr numbers) capacity counter)
             (subset-sum (cdr numbers) capacity (+ (car numbers) counter)))
         (subset-sum (cdr numbers) capacity (+ (car numbers) counter))) ;; choose car
        (t (subset-sum (cdr numbers) capacity counter)))) ;; choose cdr

Приведенный выше код отлично работает в common lisp. Но я хотел бы сделать что-то вроде приведенного ниже, потому что мне кажется, что использование let улучшит код. Но то, что я написал, зацикливается :( Это задание для вводного класса по ИИ... помогите новичку, пожалуйста!

(defun subset-sum (numbers capacity counter)
  (let ((exclude (subset-sum (cdr numbers) capacity counter))
   (include (subset-sum (cdr numbers) capacity (+ (car numbers) counter))))
     (cond ((null numbers) counter)
       ((= counter capacity) counter)
       ((< capacity (+ (car numbers) counter)) exclude)
       ((<= exclude include) include)
       (t (exclude)))))

recursion common-lisp subset-sum
person Shaun Zen    schedule 19.06.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы получаете бесконечный цикл из-за этих строк:

(defun subset-sum (numbers capacity counter)
  (let ((exclude (subset-sum (cdr numbers) capacity counter))

Вы продолжаете рекурсивно вызывать subset-sum, и он никогда не завершается. Даже когда вы дойдете до конца списка, а numbers равно (), вы продолжите, потому что (cdr '()) '(). Вы справились с этим в оригинале, проверив (пустые числа) (хотя может быть более идиоматично использовать (конечные числа)). Теперь вы можете сделать что-то вроде:

(defun subset-sum (numbers capacity counter)
  (if (endp numbers)
    counter
    (let ((exclude (subset-sum (cdr numbers) capacity counter))
          ;...
         )
      (cond ; ...
          ))))
person Joshua Taylor    schedule 19.06.2015
comment
Хорошо, теперь это работает. Насколько я понимаю, я хочу поставить базовый вариант перед использованием условного цикла с let. Огромное спасибо! - person Shaun Zen; 19.06.2015