SICP示例：计数变化，无法理解

Question

我是麻省理工学院开放式课程SICP课程的初学者，使用视频讲座和网上提供的书籍。昨天我遇到了一个例子，它问我们是否可以编写一个程序来计算改变任何给定金额的方法的数量。

这个问题有一个简单的递归解决方案：

(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

如果你想查看更多，我从这里拿走了。

他们使用K种硬币计算数量（a）的变化方式的数量（N），通过加上：

>

在没有第一种硬币的情况下，改变货币的方法（X）的数量。

改变（A-D）的方式（Y）的数量，其中D是第一枚硬币的面额，使用所有K种硬币。

问题是，我只是不明白这一点。接下来，他们试图解释说：

“要想知道为什么这是真的，可以观察到改变的方式可以分为两组：不使用任何第一种硬币的方式，和使用任何第一种硬币的方式。因此，改变某一金额的方式总数等于不使用任何第一种硬币的情况下改变金额的方式的数量，加上假设我们确实使用了第一种硬币，那么有很多方法可以改变。（最后一句与加法N=xy相同吗？）但后一个数字等于使用第一种硬币后剩余的硬币数量的改变方法的数量。（使用这种硬币后，他们指的是使用或不使用第一种硬币进行改变的方式？）"

我理解他们是如何实现递归算法的，但我不知道他们是如何实现的。英语不是我的母语，所以我可能错过了一些东西。如果你能用其他术语解释我，解决方案背后的逻辑，我将不胜感激。谢谢

Answer 1

上面威尔·内斯答案中的第一个代码框给了我足够的洞察力来理解算法。一旦我理解了它，我意识到，通过一步一步地实际观察算法的功能，我可能很快就达到了目的。

下面是一个简单案例的算法流程图。我们有两种硬币：五便士（索引2）和一便士（索引1）。

请注意，叶节点的计算结果均为0或1。当我们查看过程中的条件时（返回其中一个值，或者函数再次调用自身），这一点很明显只有两个叶节点的值为1，因此有两种方法可以从这两种硬币中获得6便士，即6便士，或1便士和5便士。

我现在理解了算法，但我仍然不知道如何从最初的问题中得出算法。也许，随着我对SICP这本书读得更多，这种解决方案对我来说会更加明显。

                             (cc 6 2)
                                |
                 -----------------------------------
                 |                                 |
              (cc 6 1)                          (cc 1 2)
                 |                                 |
   ------------------                         --------------
   |                |                         |            |
(cc 6 0)=0       (cc 5 1)                  (cc 1 1)     (cc -4 2)=0
                    |                         |
             -------------             -------------
             |           |             |           |
          (cc 5 0)=0  (cc 4 1)      (cc 1 0)=0  (cc 0 1)=1
                         |
               --------------
               |            |
            (cc 4 0)=0   (cc 3 1)
                            |
                     --------------
                     |            |
                  (cc 3 0)=0   (cc 2 1)
                                  |
                           --------------
                           |            |
                        (cc 2 0)=0   (cc 1 1)
                                        |
                                 --------------
                                 |            |
                              (cc 1 0)=0   (cc 0 1)=1

Answer 2

如果我们在递归上想得太多，我们已经失败了。就我个人而言，我在思考递归时使用了两个隐喻。其中一条来自小书《小阴谋家》：第七条戒律——重复出现在性质相同的子部分上。另一个是用于设计算法的分治结合范式。本质上，它们在如何递归思考上是相同的。

1. 分成性质相同的子部分

这个问题有两个变量：货币的数量（N）和硬币的种类（K），因此任何划分都需要满足以下条件：1。减少所有变量：N和K，2。子部分的性质相同，因此每个子部分可以通过递归过程本身求解，也可以直接求解。3.所有子部分合起来==原来的一部分，不多也不少

解决方案中的划分将原始问题分为两个子部分：第一个子部分是使用第一枚硬币的所有组合（我们可以重申，使用第一枚硬币中至少一枚硬币的所有组合具有相同的含义）。剩下的子部分是，所有组合都不使用第一枚硬币。N在第一部分中减少，K在第二部分中减少。这两个问题性质相同，可以递归求解，它们一起就是原始问题。

在这一步中，我考虑基本案例。当问题减少到最小时，可以直接给出答案的所有基本情况是什么？在这个解中，有三个基本情况。第一是N减少到0。第二是N减少到负数。第三是硬币减少到0，但N仍然是正数。

子部分求解时结果是如何组合的。在这个解决方案中，它们是简单的。

更重要的是，如果我们在一个列表上是递归的，划分通常是列表的car和列表的cdr。通常，如果列表的车本身不是列表，则可以直接求解。cdr部分应该递归求解。基本情况是列表的末尾（如果满足）。

顺便说一句，我强烈推荐学习递归的小架构器。据我所知，在这一点上，它比任何其他的都好。

Answer 3

“N种方式的数量……使用N种方式”这两个Ns显然是不同的。那么让我们假设K各种硬币。

我们有很多硬币，但每枚硬币不是1美分、5美分、10美分、25美分就是50美分，总共有5种硬币。我们需要花一美元100美分买点东西。假设每种硬币的供应都是无限的。我们有多少方法可以达到100人的总数？

我们要么使用一些50美分的硬币（一个或多个），要么不使用。如果没有，我们仍然必须在只有4种硬币的情况下到达100。但是如果我们这样做了，那么在使用了一枚50美分的硬币后，总数变成了100 - 50 = 50美分，我们仍然可以使用所有5种硬币来达到新的、更小的总数：

ways{ 100, 5 } = ways{ 100, 5 - 1 }      ;   never use any 50-cent coins
                 +                       ; OR
                 ways{ 100 - 50,  5 }    ;   may use 50-cent coins, so use one

或者总的来说，

ways( sum, k ) = ways( sum, k - 1 )
                 +
                 ways( sum - first_denomination(k),  k )

这就是全部。看见泛化自然而然地伴随着抽象（用符号代替具体的值，并将其作为函数定义中的参数）。

然后我们需要处理基本情况。如果和=0，结果是1：有一种方法可以达到总和为0（它是：不取硬币）。

如果k=0，这意味着我们不允许使用任何种类的硬币；换句话说，如果不使用至少一些硬币（除非总和为0，但我们已经处理了上面的那个案子）。所以结果一定是0。

如果sum，则相同

如果你愿意的话，从时间箭头的另一端来看。

想象一下，有人已经为你做了所有这一切，并且把这些成堆的账单放在你面前，每一堆账单加起来就是目标金额。在不失去普遍性的情况下，让每一堆都被分类，以便更大的账单在上面。

把所有的钞票分成两组：一组上面有最大面值的钞票，另一组没有。如果桩的总数是道（denomsList，targetSum），那么第二组桩的数量显然是道（rest（denomsList，targetSum）。

然后，我们可以从第一组中的每一堆上取下最上面的账单，其中的堆数显然不会因此而改变。除去每一堆中最上面的账单后，我们看到它们总计为targetSum-first（denomsList），因此它们总共对方式（denomsList，targetSum-first（denomsList））进行了编号。

（结构）递归的要点是在小范围内思考——不要试图一次描绘整个操作序列，而是站着不动，试图理解你当前的情况。它是处理你的问题的心理工具，它是关于以最简单最自然的方式解决它，尽可能小的一步。

给自己打电话（复印件）是一个技术问题。最重要的是信仰的飞跃，你可以称自己为：假设你已经写下了自己的定义，就用它来形容自己是合适的。这就是它被写下来的方式。你只需要描述你拥有的，它是如何由更小的部分组成的（其中一些类似于完整的部分），以及如何将这些部分的结果与其他部分结合起来得到完整的解决方案。

编辑（来自评论）：递归解决问题的关键是认识到它可以被分解成一系列较小的子问题，我们正在寻求的相同的通用解决程序适用于每个子问题，然后在从那些子问题的解决方案中找到一些简单的方法（通过相同的一般程序找到，就像我们已经可以使用它一样）。由此产生的每个子问题都是“较小的”，保证了基本情况最终会得到解决。

换句话说，试着找出问题的结构，使其具有与整体相似的子结构（如分形；或例如，列表的后缀也是列表；等等）；然后，递归是：假设我们已经有了解决方案；将问题分解（根据我们构建问题的方式）；通过解决方案转换“较小”子结构；然后以某种简单的方式（根据我们构建问题的方式）将所有这些结合起来。诀窍是认识到问题中存在的固有结构，以便自然地找到解决方案。

或者，在Prolog中（所有编程语言中：）：

recursion(       In,  Out) :- 
  is_base_case(  In), 
  base_relation( In,  Out).

recursion(       In,  Out) :- 
  not_base_case( In),
  constituents(  In,   SelfSimilarParts,       LeftOvers),  % (* forth >>>    *)
  maplist( recursion,  SelfSimilarParts,
                             InterimResults),
  constituents(       Out,   InterimResults,   LeftOvers).  % (* and back <<< *)

也就是说，在伪代码中，

(In <--> Out) are related by recursion when
   either
      In is indivisible, and Out its counterpart
   or
      In  =  Sub_1 <+> Sub_2 <+> ... <+> Sub_N  <++>  Shell
             ------  r e c u r s i o n  ------
      Out =  Res_1 {+} Res_2 {+} ... {+} Res_N  {++}  Shell
        where
        (Sub_i <--> Res_i) ,  for each  i = 1, ..., N

In和Out的组合操作可能不同，因为它们可以是不同类型的值。