(Lisp) 我可以让它更有效率吗？

Question

计算更改样式问题，我用 lisp 编写了这个递归函数，我想知道是否有人有任何提示可以提高效率？如果数字太大，它就会开始崩溃，大约需要 3 分钟才能计算出 10 英镑的不同组合！给我指明正确的方向就好了，谢谢！

(defun dollars (amount &optional (coins '(5 10 20 50 100 200 500 1000 2000 5000 10000)))
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= (length coins) 0) (> amount 30000)) 0)          
        ((zerop (mod amount 5))
         (+ (dollars (- amount (first coins)) coins)
            (dollars amount (rest coins))))))

Answer 1

让我们来看一个类似的问题，计算斐波那契数列。

(defun fib (n)
  (if (<= 0 n 1)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

随着 n 变大，计算较小的斐波那契数的次数呈指数增长。在计算 F(10) 时，F(5) 总共计算了八次不同的时间。在计算F(15)时，F(5)一共计算了89次！我们可以通过在计算后保存一个值来解决这个问题。然后，当我们需要确定一个我们已经计算出的值时，只要查一下就可以了。下面的代码就是这样做的。

(defparameter *calculated* (make-hash-table))

(defun fib (n)
  (or (gethash n *calculated*)
      (setf (gethash n *calculated*)
            (if (<= 0 n 1)
                n
                (+ (fib (- n 1))
                   (fib (- n 2)))))))

当给定一个数进行计算时，如果代码已经计算出它，则查找它的值，否则代码将计算出该值并存储它。现在当我们计算 F(15) 时，F(5) 只计算一次，因为每隔一次它的值只是在 hash-table 中查找。由于每个斐波那契数（从 F(0) 到 F(15)）只计算一次，因此这提供了显着的加速。

这是一种称为“dynamic programming”的技术，其中从较小的值计算较大的值，然后一遍又一遍地计算较小的值。简单的解决方案是在计算时只存储一个值，并检查是否已经计算了一个值。如何将此技术应用于您自己的代码应该很简单。

(Lisp) 我可以让它更有效率吗？

(Lisp) Can i make this more efficient?

lisp

recursion

performance

common-lisp