Common Lisp：使用 (let) 评估递归函数

Question

所以我写了一些东西 returns 给定正整数列表的最大子集和。但是，我想使用 (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

上面的代码在普通的 lisp 中运行良好。但是，我想做类似下面的事情，因为我觉得使用 let 会使代码更好。但是我写的东西进入了无限循环:( 这是介绍性 AI 的作业 class...请帮助新手！

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

Answer 1

由于这些行，您得到一个无限循环：

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

你一直递归地调用 subset-sum，它永远不会终止。即使你到达列表的末尾，并且 numbers 是 ()，你继续前进，因为 (cdr ' ()) 是 '()。您在原始版本中通过检查 (null numbers) 来处理此问题（尽管使用 (endp numbers) 可能更惯用）。现在您可以执行以下操作：

(defun subset-sum (numbers capacity counter)
  (if (endp numbers)
    counter
    (let ((exclude (subset-sum (cdr numbers) capacity counter))
          ;...
         )
      (cond ; ...
          ))))

Common Lisp：使用 (let) 评估递归函数

Common Lisp: Using (let) for evaluating recursive function

recursion

common-lisp

subset-sum