Common Lisp: Using (let) for evaluating recursive function

Question

So I wrote something that returns a maximal subset sum given a list of positive integers. However, I would like to use the (let) so that I make the code more efficient. I would like to know if or how that is possible.

(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

The above code works fine in common lisp. But, I would like to do something like below, because I feel like using let will make the code better. But what I wrote goes into an infinite loop :( This is an assignment for an introductory AI class... help out a novice please!

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

Joshua Taylor Joshua Taylor · Accepted Answer · 2015-06-19T03:06:23

You get an infinite loop because of these lines:

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

You keep calling subset-sum recursively, and it never terminates. Even when you get to the end of the list, and numbers is (), you keep going, because (cdr '()) is '(). You handled this in the original by checking (null numbers) (though it might be more idiomatic to use (endp numbers)). Now you can do something like:

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

Common Lisp: Using (let) for evaluating recursive function

1 Answers