递归真是个既抽象又好玩的东西。

今天我们要讨论作业3中的三道递归问题。

第一题：interleaved_sum

和普通的递增不同，这次的这个函数的要求是：

从1开始到n，如果是奇数项，那就加上odd_func(x)；如果是偶数项，那就加上even_func(x)。

这个函数的开头是输入是数字n，odd_func和even_func。

按理说这里可以用%判定奇偶数，但题目不让（摊手）。

所以，我们需要定义两个helper函数：一个负责在奇数项调用偶数项函数，一个负责在偶数项调用奇数项函数。

互递归……

代码如下：

第二题：count_dollars

给定正整数total，找出用纸币面额（1 5 10 20 50 100）组合的种类数量。

实际上这是课程教材中例子的改版。

具体可以看：

https://composingprograms.netlify.app/1/7#_1-7-5-%E7%A4%BA%E4%BE%8B-%E5%88%86%E5%89%B2%E6%95%B0

当然，因为我们还没学到列表，所以不能使用列表。这里有另一个好东西，是作业里给出的函数。

提示说我们可以写一个helper函数。呃，那我们就写一个试试看？

首先，如果total==0，那就说明我们已经找到了一种组合方式，返回1（正好合适！）；

如果total<0，那就说明这种组合不合理，返回0（我们的组合大于要求）；

最后，如果我们已经循环到最小面值1了，next_smaller_dollar(1)是None，这时候也该停下了，return 0（我们的组合小于要求）。

最后，这个helper函数需要使用树递归的方法，既自己往下减，还要对更小面值也进行尝试。

最终代码如下：

The Tower of Hanoi 问题

如图所示，有ABC三根杆子，每根杆子上串了几片圆盘。

最初，圆盘在某根杆子上，从下到上，从大到小排列。

目标是把所有的圆盘移动到另一根杆子上，依然是从下到上从大到小排列。

需要遵循以下两条规则：

1. 每次只能移动一根柱子最上方的（也就是最小的）一个圆盘。

2. 大圆盘不能在小圆盘上。

目标是写一个函数，把n层的塔的移动过程全部打印出来。

实际上，解决The Tower of Hanoi的方法是固定的。

分解思路如下：如果我们想把整个河内塔移动到目的地，那就得先把河内塔的底座（最底下的圆盘）移到目的地。

那么上面的部分该怎么办呢？我们可以先把它当作另一个小一点的塔，把它移动到除了目的地和起始地的第三根杆子上。

然后等底盘移动完毕之后，再把这座小一层的河内塔从第三根杆子上移动到目的地上去。

也就是说，我们把一个移动河内塔的问题，转化为了两次移动更小一层河内塔的问题。

并且，由于我们始终在移动更小的河内塔，不用担心下克上的问题。

那么解决方案就很明确了：递归。

print_move函数是作业中自带的用来打印步骤的函数。

由于我们的目标是把移动的过程完全打印出来，我们必然是需要用到这个函数的。

那么，何时用到呢？当然是在移动一块圆盘的时候，或者，用递归函数来说，就是移动单层河内塔的时候。所以函数中可以写上，当n=1的时候，调用print_move。

而当n>1的时候，我们需要让这个函数递归下去，具体来说，就是执行上述提到的三步：移到第三根，把底盘移到目标，从第三根移到目标。

下一个问题是：所谓的“第三根柱子”到底是什么？

如果我们的目标是把一个足够大的(n≥3)河内塔从1号移动到2号，那么“第三根柱子”就是3号。

但是！在这个移动过程中，我们需要先把小一层的河内塔从1号移动到3号，而这个过程中用到的“第三根柱子”就是2号。

因此我们可以在这个函数中定义一个helper函数，找到所谓的“第三根柱子”到底是谁。

f(1,3)=2; f(1,2)=3; f(2,3)=1

很显然，我们可以直接取f(x,y)=6-x-y

这样我们就能随时找到“第三根柱子”了。

综合以上，我们可以写出下面的move_stack这个递归函数。

稍微写一点总结吧……

递归真是个麻烦的东西。它实在是太不符合我这样的凡人的思维方式了……

但是真的写完之后，并且理解之后，有一种尤里卡的醍醐灌顶感。原来这么巧妙的吗？