我们人类的固有思维方式常常是出于直观的，由近及远、从少到多，这样的思维方式让我们很容易理解具体的事物，却也限制了我们的抽象思维，所以当我们理解远离我们生活经验的事物时，就容易出现障碍。我们人类这种自底向上、从小到大的正向思维，称为“递推思维”。但是“计算思维”则不同，它是一种自顶向下、先全局后局部的逆向思维方式，被称为“递归思维”。作为计算机工程的从业者，我们经常需要从递推思维中抽离出来，转换到计算思维，这就需要我们能够很好地应用递归思想。
相对于我们固有的递推思维，递归思维有两个明显的优势。第一个是，只要解决当前一步的问题，就能解决全部的问题；第二个是，剩余的问题，复制处理当前问题的同一过程即可。当然，这里有两个前提条件：(1) 每一个问题在形式上都是相同的，否则无法通过同一个过程完成不同阶段的计算；(2) 必须有一个结束条件。
虽然在多年前已经接触过递归思想，但当时并没有get到它的妙处，而且还颇以为难以理解，只是应付任务式的使用。现在来读吴军老师的这本书，竟然有种相见恨晚的感觉，边读边不由自主地动手写起代码来了。写都写了，那就来复现两个书中的例题吧。
这个题如果从正向递推考虑，其实挺难的，很快思维就乱了。那我们试试用递归的方式来解决。
假定到第20级台阶有F(20)种不同的路径，那么到20之前，按照题目的说法，有1级和2级两种走法，也就是F(20) = F(19) + F(18)，以此类推，每个当前台阶的上一步，都有两种走法。所以我们就可以给出一个普遍公式：F(n) = F(n-1) + F(n-2)，其中，F(1) = 1, F(2) = 2，(这是因为，到第一级台阶只有1种走法，到第二级台阶有两种走法)。
上代码，为了简单，用Python实现的。
def func(n):
assert(n >= 1)
if n == 1:
return 1
elif n == 2:
return 2
else:
return func(n - 1) + func(n - 2)
print("func(20) = ", func(20)) 运行结果：
func(20) = 10946
与书上的结果一致。
再来看第二个问题，汉诺塔问题。
N=1的时候比较直观，直接将唯一的盘子从A柱移到B柱即可；
N=2的时候也比较简单，先把第一个盘子（最上面的小盘子）从A柱放到T柱，再把第二个盘子（下面的大盘子）从A柱移到B柱，最后把T柱上的小盘子再放到B柱上。
N>=3的时候，就越来越复杂了。
所以接下来，我们还是应用递归思想，要移动最下面的第N个盘子，必须先把上面的N-1个盘子移动到T柱；移动完第N个盘子之后，还要把T柱上的N-1个盘子借助A柱再移动到B柱。重复这个过程，一直到完成移动。
继续上代码：
# Move n dishes from A to B, with T is a middle transfer
# The bigger dishes must be placed under the smaller ones in each column
def Hanoi(n, A, B, T):
if n > 0:
Hanoi(n-1, A, T, B)
print('move dish {} from {} to {}'.format(n, A, B))
Hanoi(n-1, T, B, A)
Hanoi(4, 'A', 'B', 'T')
简单起见，测试了1~5个盘子的移动，其中，4个盘子的移动顺序如下：
是不是简洁又完美！