SICP例子：计数变化，看不懂
SICP example: Counting change, cannot understand
我是麻省理工学院 OpenCourseWare 上的 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)))
如果你想查看更多内容，我从 here 中获取了它。
他们正在计算使用 K 种硬币改变数量 (A) 的方法的数量 (N)，方法是添加：
没有第一种硬币的情况下改变A的方式（X）的数量。
兑换（A - D）的方式（Y）的数量，其中D是第一枚硬币的面额，使用所有K种硬币。
问题是，我就是不明白这一点。接下来，他们试图解释说：
"To see why this is true, observe that the ways to make change can be divided into two groups: those that do not use any of the first kind of coin, and those that do. Therefore, the total number of ways to make change for some amount is equal to the number of ways to make change for the amount without using any of the first kind of coin, plus the number of ways to make change assuming that we do use the first kind of coin. (Is the last sentence the same as the addition N = X + Y ? ) But the latter number is equal to the number of ways to make change for the amount that remains after using a coin of the first kind. (After using this coin, they refer to ways of making change with or without the first kind of coin? ) "
我了解他们是如何实现递归算法的，但我看不到他们是如何实现的。
英语不是我的母语，所以我可能会遗漏一些东西。如果您能使用其他术语向我解释解决方案背后的逻辑，我将不胜感激。谢谢
"number (N) ways ... using N kinds"这两个N显然不一样。所以假设 K 种硬币。
我们有很多硬币，但是每个硬币是1、5、10、25或50分，一共5种硬币。我们需要花 1 美元，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 )
仅此而已。看？泛化自然而然地伴随着抽象（用符号替换具体值并使它们成为函数定义中的参数）。
然后我们需要处理基本情况。如果sum = 0，结果是1：有一种方法可以达到总和为0（就是：不拿硬币）。
如果k = 0，这意味着我们不允许使用任何种硬币；换句话说，如果不使用至少 some 个硬币（除非总和为 0，但是我们已经在上面处理过这种情况）。所以结果一定是0.
当然，sum < 0也是一样。不可能，即 0 种方法来总结它，使用任何正面额的硬币。
另一种方式是从时间箭头的另一端看。
想象一下，有人已经为您完成了所有这些工作，并把所有这些成堆的账单放在您面前，每一堆的总和都是目标金额。不失一般性，对每一堆进行排序，以便较大的钞票在最上面。
将所有纸币分成两组：一组在每堆上面放最大面额的钞票，另一组没有。如果总桩数是ways( denomsList, targetSum)，那么显然第二组的桩数是ways( rest(denomsList), targetSum).
然后，我们可以从第一组中的每堆中取出最上面的钞票，并且其中的堆数显然不会因此而改变。移除每堆最上面的钞票后，我们看到它们的总和为 targetSum - first(denomsList)，因此它们的总数为 ways( denomsList, targetSum - first(denomsList))。
（结构）递归的要点是从小处思考——不是试图一次描绘出整个操作序列，而是站在原地并试图理解你的当前情况。它是解决您的问题的一种心理工具，它是关于以最简单最自然的方式解决问题，使 尽可能小的步骤。
调用（a copy of) yourself is a technicality. The main thing is the leap of faith, that you are allowed to call yourself: assuming you have already written down your definition, just use it were appropriate. And that's how it gets written down。你只需描述你所拥有的，它是如何由更小部分组成的（其中一些相似 到完整的东西），以及如何将 那些 部分的 结果 与其余部分组合起来以获得完整的解决方案。
edit（来自评论）：递归解决问题的关键是认识到它可以分解为更小的子问题的集合，每个子问题 我们正在寻求的相同通用求解程序适用，然后从这些子问题的解决方案（其中是通过相同的一般程序找到的，就好像我们已经可以使用它一样）。这样创建的每个子问题都“更小”，保证最终会达到基本情况。
换句话说，尝试找到问题中的结构，使其具有与整体相似的子结构（如分形；或者例如列表的后缀也是列表；等等）；那么，递归是：假设我们已经有了解决方案； 将问题实例分开（根据我们构建问题的方式）； 转换 “更小” 子结构；然后组合所有返回以某种简单方式（根据我们构建我们的方式问题）。诀窍是识别问题中 现有的 固有结构，以便自然而然地找到解决方案。
或者，在 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 的组合操作 + 可能不同，因为它们可以是不同类型的值。
如果我们对递归考虑太多，我们已经失败了。就个人而言，我在思考递归时使用了两个比喻。一本来自小书"the little schemer"：The Seventh Commandment - Recur on the subparts that are of the same nature。另一种是设计算法的分而治之的范式。从本质上讲，它们在如何递归思考方面是一样的。
- 划分为相同性质的子部分
问题有两个变量：钱的数量（N）和硬币的种类（K），因此任何划分都需要满足以下条件：1. reducing all variables: both N and K, 2. the subparts are the same nature so each subpart can be solved by the recursion process itself or be can solved directly. 3. all subparts together == the original one part, no more and no less.
解中的划分将原题分为两个子部分：第一个子部分是所有使用第一个硬币的组合（我们可以重申一下，所有使用第一个硬币中至少一个硬币的组合具有相同的意义).剩下的子部分是所有使用第一个硬币的 none 的组合。 N在第一部分减少，K在第二部分减少。两者性质相同，可以递归求解，合起来就是原问题
- 征服
在这一步中，我考虑了基本情况。当问题减少到可以直接给出答案的最小值时，所有基本情况是什么？在此解决方案中，存在三种基本情况。第一个是 N 减少到 0。第二个是 N 减少到负数。第三个是硬币减少到0但N仍然是正数。
- 合并
解决子部分时如何合并结果。在此解决方案中，它们只是 +.
另外，如果我们对一个列表进行递归，划分通常是列表的car和列表的cdr。通常car of list如果本身不是list可以直接求解。 cdr 部分应该递归地解决。如果满足，则基本情况是列表的末尾。
B.T.W，我强烈推荐 the little schemer 来学习递归。就我所读的而言，在这一点上它比任何其他的都要好。
上面 Will Ness 的回答中的第一个代码框让我有足够的洞察力来理解算法。一旦我理解了它，我意识到我可能会通过实际逐步了解算法的作用很快达到目标。
下面是算法如何处理一个简单案例的图表。金额是 6 便士，我们有两种硬币：五便士（索引 2）和一便士（索引 1）。
请注意，叶节点的计算结果均为 0 或 1。当我们查看过程中的条件时，这一点很明显（返回这些值之一，否则函数将再次调用自身。）只有两个叶节点求值为1，所以这两种硬币有2种方法可以变成6便士，即6便士，或者一便士和五便士。
我现在理解了算法，但我仍然不明白如何从最初的问题中得出算法。也许，随着我阅读更多 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
我是麻省理工学院 OpenCourseWare 上的 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)))
如果你想查看更多内容，我从 here 中获取了它。
他们正在计算使用 K 种硬币改变数量 (A) 的方法的数量 (N)，方法是添加：
没有第一种硬币的情况下改变A的方式（X）的数量。
兑换（A - D）的方式（Y）的数量，其中D是第一枚硬币的面额，使用所有K种硬币。
问题是，我就是不明白这一点。接下来，他们试图解释说：
"To see why this is true, observe that the ways to make change can be divided into two groups: those that do not use any of the first kind of coin, and those that do. Therefore, the total number of ways to make change for some amount is equal to the number of ways to make change for the amount without using any of the first kind of coin, plus the number of ways to make change assuming that we do use the first kind of coin. (Is the last sentence the same as the addition N = X + Y ? ) But the latter number is equal to the number of ways to make change for the amount that remains after using a coin of the first kind. (After using this coin, they refer to ways of making change with or without the first kind of coin? ) "
我了解他们是如何实现递归算法的，但我看不到他们是如何实现的。 英语不是我的母语，所以我可能会遗漏一些东西。如果您能使用其他术语向我解释解决方案背后的逻辑，我将不胜感激。谢谢
"number (N) ways ... using N kinds"这两个N显然不一样。所以假设 K 种硬币。
我们有很多硬币，但是每个硬币是1、5、10、25或50分，一共5种硬币。我们需要花 1 美元，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 )
仅此而已。看？泛化自然而然地伴随着抽象（用符号替换具体值并使它们成为函数定义中的参数）。
然后我们需要处理基本情况。如果sum = 0，结果是1：有一种方法可以达到总和为0（就是：不拿硬币）。
如果k = 0，这意味着我们不允许使用任何种硬币；换句话说，如果不使用至少 some 个硬币（除非总和为 0，但是我们已经在上面处理过这种情况）。所以结果一定是0.
当然，sum < 0也是一样。不可能，即 0 种方法来总结它，使用任何正面额的硬币。
另一种方式是从时间箭头的另一端看。
想象一下，有人已经为您完成了所有这些工作，并把所有这些成堆的账单放在您面前，每一堆的总和都是目标金额。不失一般性，对每一堆进行排序，以便较大的钞票在最上面。
将所有纸币分成两组：一组在每堆上面放最大面额的钞票，另一组没有。如果总桩数是ways( denomsList, targetSum)，那么显然第二组的桩数是ways( rest(denomsList), targetSum).
然后，我们可以从第一组中的每堆中取出最上面的钞票，并且其中的堆数显然不会因此而改变。移除每堆最上面的钞票后，我们看到它们的总和为 targetSum - first(denomsList)，因此它们的总数为 ways( denomsList, targetSum - first(denomsList))。
（结构）递归的要点是从小处思考——不是试图一次描绘出整个操作序列，而是站在原地并试图理解你的当前情况。它是解决您的问题的一种心理工具，它是关于以最简单最自然的方式解决问题，使 尽可能小的步骤。
调用（a copy of) yourself is a technicality. The main thing is the leap of faith, that you are allowed to call yourself: assuming you have already written down your definition, just use it were appropriate. And that's how it gets written down。你只需描述你所拥有的，它是如何由更小部分组成的（其中一些相似 到完整的东西），以及如何将 那些 部分的 结果 与其余部分组合起来以获得完整的解决方案。
edit（来自评论）：递归解决问题的关键是认识到它可以分解为更小的子问题的集合，每个子问题 我们正在寻求的相同通用求解程序适用，然后从这些子问题的解决方案（其中是通过相同的一般程序找到的，就好像我们已经可以使用它一样）。这样创建的每个子问题都“更小”，保证最终会达到基本情况。
换句话说，尝试找到问题中的结构，使其具有与整体相似的子结构（如分形；或者例如列表的后缀也是列表；等等）；那么，递归是：假设我们已经有了解决方案； 将问题实例分开（根据我们构建问题的方式）； 转换 “更小” 子结构；然后组合所有返回以某种简单方式（根据我们构建我们的方式问题）。诀窍是识别问题中 现有的 固有结构，以便自然而然地找到解决方案。
或者，在 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 的组合操作 + 可能不同，因为它们可以是不同类型的值。
如果我们对递归考虑太多，我们已经失败了。就个人而言，我在思考递归时使用了两个比喻。一本来自小书"the little schemer"：The Seventh Commandment - Recur on the subparts that are of the same nature。另一种是设计算法的分而治之的范式。从本质上讲，它们在如何递归思考方面是一样的。
- 划分为相同性质的子部分
问题有两个变量：钱的数量（N）和硬币的种类（K），因此任何划分都需要满足以下条件：1. reducing all variables: both N and K, 2. the subparts are the same nature so each subpart can be solved by the recursion process itself or be can solved directly. 3. all subparts together == the original one part, no more and no less.
解中的划分将原题分为两个子部分：第一个子部分是所有使用第一个硬币的组合（我们可以重申一下，所有使用第一个硬币中至少一个硬币的组合具有相同的意义).剩下的子部分是所有使用第一个硬币的 none 的组合。 N在第一部分减少，K在第二部分减少。两者性质相同，可以递归求解，合起来就是原问题
- 征服
在这一步中，我考虑了基本情况。当问题减少到可以直接给出答案的最小值时，所有基本情况是什么？在此解决方案中，存在三种基本情况。第一个是 N 减少到 0。第二个是 N 减少到负数。第三个是硬币减少到0但N仍然是正数。
- 合并
解决子部分时如何合并结果。在此解决方案中，它们只是 +.
另外，如果我们对一个列表进行递归，划分通常是列表的car和列表的cdr。通常car of list如果本身不是list可以直接求解。 cdr 部分应该递归地解决。如果满足，则基本情况是列表的末尾。
B.T.W，我强烈推荐 the little schemer 来学习递归。就我所读的而言，在这一点上它比任何其他的都要好。
上面 Will Ness 的回答中的第一个代码框让我有足够的洞察力来理解算法。一旦我理解了它，我意识到我可能会通过实际逐步了解算法的作用很快达到目标。
下面是算法如何处理一个简单案例的图表。金额是 6 便士，我们有两种硬币：五便士（索引 2）和一便士（索引 1）。
请注意，叶节点的计算结果均为 0 或 1。当我们查看过程中的条件时，这一点很明显（返回这些值之一，否则函数将再次调用自身。）只有两个叶节点求值为1，所以这两种硬币有2种方法可以变成6便士，即6便士，或者一便士和五便士。
我现在理解了算法，但我仍然不明白如何从最初的问题中得出算法。也许，随着我阅读更多 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