最近刚开始算法学习，对递归思想非常着迷，做project euler时遇到题目就想用递归处理一下，但总的来说吃力不讨好。倒是今天给我找到一个绝佳的例子，相比于暴力破解，用递归重写后的代码轻巧了许多，可读性也增强了。

题目

project euler 31题:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way: 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

暴力破解1

看到题目最自然的想法是穷举一下所有的组合，检测和是不是200。

这是非常原始的暴力破解方法，好处是不需要进一步的思考，非常容易写，且保证能得到正确结果。这几点好处——尤其是保证能得到正确结果是后面优化的基石——使得这种粗陋的代码也有写出来的价值。

当然，缺点是效率不理想，一般不会作为最终版本来使用。这里还好，只用了三四分钟，有时则可能要几个月，那就不得不立刻开始优化了。

代码：

def coin():
    counter = 0
    for i100 in range(3):
        item100 = 100 * i100
        print "100:", i100
        for i50 in range(5):
            item50 = 50 * i50
            print "50:", i50
            for i20 in range(11):
                item20 = 20 * i20
                for i10 in range(21):
                    item10 = 10 * i10
                    for i5 in range(41):
                        item5 = 5 * i5
                        for i2 in range(101):
                            item2 = 2 * i2
                            for i in range(201):
                                if item100 + item50 + item20 + item10 + item5 + item2 + i == 200:
                                    counter += 1
    return counter

上面的代码没有考虑只取200分的情况，所以得到的结果加上1才是正确答案。

暴力破解2

project euler前面的题目都比较简单，根据经验，算法得当的话运算时间都可以轻松压在毫秒级，上面的代码算了几分钟是不可忍受的。

问题显然在于计算了太多本不需要的计算的可能，所谓优化，不过是不需要算的部分直接不算了，具体到这个问题上，上面是先列举可能，再测试是否符合要求，其实可以反过来处理，你不是要200吗，那就从里面往外减，什么时候减没了算完。

所以代码可以写成：

def coin2():
    counter = 0
    item200 = 200
    while item200 >= 0:
        item100 = item200
        while item100 >= 0:
            item50 = item100
            while item50 >= 0:
                item20 = item50
                while item20 >= 0:
                    item10 = item20
                    while item10 >= 0:
                        item5 = item10
                        while item5 >= 0:
                            item2 = item5
                            while item2 >= 0:
                                counter += 1
                                item2 -= 2
                            item5 -= 5
                        item10 -= 10
                    item20 -= 20
                item50 -= 50
            item100 -= 100
        item200 -= 200
    return counter

好消息是效率提升不少，现在只需要16ms就可以搞定。

但依旧是8曾循环嵌套，烧脑子可读性差容易出错就不说了，这里问题简单些只要8层就能解决问题，可如果遇到更多的呢？你能写出来解释器也吃不消吧。

递归

这种问题很适合用递归来处理，先不多说，看代码：

def coin3(l=[200, 100, 50, 20, 10, 5, 2, 1], target=200):
    counter = 0
    if len(l) == 1:
        return 1
    while target >= 0:
        counter += coin3(l[1:], target)
        target -= l[0]
    return counter

刚写出来的时候我也不相信，之前繁琐的代码竟然可以变的如此漂亮，但算出来的答案是一样的，不骗你。唯一的缺点是用递归慢一些。

那这是怎么正常工作的？

设想我们有一个一般化的处理方案，函数coin(l, target)，吃进去一个包含了所有可取的硬币额度和一个最终需要的总数，吐出来的就是所有可能的组合方案，没错这就是我们要的。

但这个函数怎么写呢？下面一步很关键。

主要用到了分而治之的战略思想。先考虑一个简单的例子，coin([5, 2, 1], 10)，很容易发现有10种可能，问题在于使用了怎样的解题思路。

一个保证不漏掉可能的思路是先考虑到底有取了多少个5分，显然只能是0或1或2，如果是0的话，问题被简化为求coin([2, 1], 10)，同理，如果是1的话问题简化为求coin([2, 1], 5)；最后只需要把几种情况下的可能加起来就是最终结果了。

这就是递归处理的思路，每次只处理一个候选项，并将简化了的问题通过自己调用自己的方式解决，一路下来正确答案就自己跳出来了。

唯一需要留心的是这种递归调用终结在什么地方，稍微思考一下就会发现，是整个问题最基础最简单的情形，这样解决起来也不费什么功夫了。

再看一眼

其实递归的思路和第二版的暴力破解是一样的，但得益于函数可以自我调用这一特点，代码被大大简化了。

就好比没有循环之前你想求1到100的求和只能老老实实一步一步去写，用上循环则只需要三行。

用递归的好处在于，问题被一般化了，8曾循环是这样写，100层还是这样写（只要不爆栈的话...）。代码思路变得更加清晰，可读性更好，出错的机会就小了。

但递归这种思想和人脑的工作方式有悖，所以理解也好、使用也罢并不是那么自然，需要训练。

不管如何这都是一种强大的处理问题的思路，值得好好斟酌一番。

一点补充

上面的代码其实还取了一个巧，因为最后一个选项是1，所以不管前面怎么分配，到最后一步时总能找到一个符合要求的结果，所以索性不算了。如果要处理更一般的情况，则还需要一些改动。