optimization - SICP做出改变

Question

所以;我是一个试图通过 SICP ( it's free! ) 工作的爱好者，第一章中有一个示例程序，旨在计算使用美国硬币进行找零的可能方法； (change-maker 100) => 292. 它的实现如下:

(define (change-maker amount)
  (define (coin-value n)
    (cond ((= n 1) 1)
          ((= n 2) 5)
          ((= n 3) 10)
          ((= n 4) 25)
          ((= n 5) 50)))

  (define (iter amount coin-type)
    (cond ((= amount 0) 1)
          ((or (= coin-type 0) (< amount 0)) 0)
          (else (+ (iter amount
                         (- coin-type 1))
                   (iter (- amount (coin-value coin-type))
                         coin-type)))))

  (iter amount 5))

无论如何；这是一个树递归过程，作者“留下作为挑战”寻找迭代过程来解决相同的问题(即固定空间)。在感到沮丧后，我没有幸运地弄清楚这一点或找到答案。我想知道这是我的脑放屁，还是作者在耍我。

Answer 1

通常，消除递归的最简单/最通用的方法是使用辅助堆栈——而不是进行递归调用，而是将它们的参数插入堆栈并进行迭代。当您需要递归调用的结果以便继续时，同样在一般情况下，这有点复杂，因为您还必须能够推送“继续请求”(这将脱离辅助结果已知时堆叠)；但是，在这种情况下，由于您对所有递归调用结果所做的只是求和，因此保留一个累加器就足够了，并且每次获得数字结果而不需要进行更多调用时，将其添加到蓄能器。

然而，这本身并不是固定的空间，因为该堆栈会增长。所以另一个有用的想法是:因为这是一个纯函数(没有副作用)，任何时候你发现自己已经为某个参数集计算了函数的值，你可以 memoize 参数-结果对应关系。这将限制调用次数。另一个导致几乎相同计算的概念方法是 dynamic programming [[aka DP]]，尽管使用 DP，您经常自下而上地“准备要内存的结果”，可以这么说，而不是从递归开始并努力消除它。

以这个函数的自底向上DP为例。你知道你会反复得到“有多少种方法可以用最小的硬币来改变数量 X”(当你用原始 amount 的各种硬币组合将东西减少到 X 时)，所以你开始计算这些 amount 值用一个简单的迭代(f(X) = X/value 如果 X 可以被最小硬币值整除 value ，否则 0 ；这里，value 是 1，所以 f(X)=X 对于所有 X>0)。现在你继续计算一个新函数 g(X)，用两个最小的硬币改变 X 的方法:同样是增加 X 的简单迭代，g(x) = f(X) + g(X - value)对于第二小的硬币的 value(这将是一个简单的迭代，因为在您计算 g(X) 时，您已经计算并存储了 f(X) 和所有 g(Y) 的 Y < X - - 当然，对于所有 X <= 0，g(X) = 0)。再次对于 h(X)，用三个最小的硬币给 X 找零的方法—— h(X) = g(X) + g(X- value ) 如上所述——从现在开始你就不需要了f(X) ，所以你可以重用那个空间。总而言之，这需要空间 2 * amount —— 还不是“固定空间”，但是，越来越近了……

为了向“固定空间”迈出最后一步，问问自己:您是否需要在每一步都保留两个数组的所有值(上次计算的一个和当前正在计算的一个)，或者只保留其中的一些值值，通过重新排列你的循环一点点......？