1.2.2 换零钱的递归例子
- 换零钱作为树型递归的第二个例子，它比fib数难的一点在于需要判断什么时候返回有效值（也就是1），如何从现实问题抽象出递归模型。
重温下题目：
给了半美元，四分之一美元，10美分，5美分，1美分的硬币，将1美元换成零钱，一共有多少种换法？
将这个题目一般化，是这么一个问题：
将总数为a的现金换成n种硬币，问有多少种不同换法？
这个问题，可以规约为下面两个子问题：
- 将现金a换成除第一种硬币以外的其他硬币的不同方式，加上
- 将现金a－d换成所有种类硬币的不同方式。其中d为第一种硬币的面值。
子问题1减少了硬币种类，子问题2减少了现金数。子问题比原问题范围要小，终止条件如下：
- a=0时，说明已经成功将现金换完，算是一种有效换法
- a<0时，说明当前的现金比要兑换硬币面值小，不是有效换法
- n=0时，说明当前的现金无法兑换硬币了，不是有效换法。
上面三种情况，第三种不是很明显，下面说一个例子：
假如现在我们不能使用1美分的硬币，而现金还剩3美分，那么其他硬币也就无法兑换了。
(define (exchange amount)
(cc amount 5))
(define (cc amount kind)
(cond
((= amount 0) 1)
((or (< amount 0) (= 0 kind)) 0)
(else
(+ (cc amount (- kind 1))
(cc (- amount (kinds-of-coins kind)) kind)))))
(define (kinds-of-coins kind)
(cond
((= kind 5) 50)
((= kind 4) 25)
((= kind 3) 10)
((= kind 2) 5)
((= kind 1) 1)))
(exchange 100)
;Value: 292
换硬币问题我们用递归的方式相对来说解决还不是很难，但是如何用迭代方式解决呢？
首先需要明确的是，所有能用递归方式实现的过程应该都能用迭代方式实现，因为所有的过程在计算机中执行的都是按照图灵机方式（前进、跳转、判断）执行的，我们能不能想出来那又是另一会事了。
迭代方式我现在还没想出来，这里延伸下，这个问题和0-1背包问题很类似，可以类比考虑。
在网上找到了，一个比较合理的迭代解法。
如果改变kinds-of-coins中硬币的顺序，程序还正确吗？时空复杂度变了吗？
找零钱问题的复杂度分析可参考习题1.14：（n为现金数）
- 时间复杂度O(n)
- 空间复杂度2n
改变kinds-of-coins中硬币的顺序，并不会改变找零钱问题算法树形递归的高度，所以时空复杂度不变。 程序当然也是正确的了，还是符合上面的条件：
- 将现金a换成除第一种硬币以外的其他硬币的不同方式，加上
- 将现金a－d换成所有种类硬币的不同方式。其中d为第一种硬币的面值。