recursion - 使用面额列表计算方案变化

Question

我正在编写一个函数来计算在给定面额列表和金额的情况下改变方案的方式的数量。我的代码如下，但它没有按预期工作。我应该使用 cons 而不是 + 运算符吗？第三行的基本情况应该是空列表吗？

(define (change k l)
 (cond ((= k 0) 1)
     ((or (< k 0) (null? l)) 0)
     (else (+ (change k (cdr l))
              (change (- k (car l))
                      (cdr l)))))) 

测试：

(change 11 (list 1 5 10 25))

Answer 1

如果返回的值只是一个数字，那么忘记cons和'()来构建输出，而只使用car,cdr来null?处理输入。除此之外，请注意代码的最后一行有一个小错误，这里是固定版本：

(define (change k l)
  (cond ((= k 0) 1)
        ((or (< k 0) (null? l)) 0)
        (else
         (+ (change k (cdr l))
            (change (- k (car l)) l))))) ; don't do (cdr l) here

现在它按预期工作：

(change 11 (list 1 5 10 25))
=> 4