前言

递归是一种非常非常重要的编程思想，它可以把复杂的问题拆分成一个一个的子问题。虽然它并没有性能上的优势，甚至还有时候比循环的性能更糟糕，但是由于它在部分场合要比简单暴力的循环要容易理解得多，所以它仍然具有一定的学习价值。

汉诺塔问题(Hanoi)

想必很多朋友都玩过这种玩具，三个柱子，以及若干个从大到小的带孔圆盘，大的盘不可以放在小的盘上，盘必须套在柱子上，不可以放到一边，一次只能移动一个盘到另一个柱子上，如何让操作最省，将汉诺塔从最左边的柱子移向最右边的柱子呢？
我们来看一下笔者亲自画的图例（顺便一说，我研究了很久才搞明白如何搭建免费图床，如果后面有时间我也会写一个引用图片的教程）
hanoi

这里有两个圆盘，也就是二阶的汉诺塔。
这里很简单，先把红色盘移到中间的柱子，再将黄色盘移到最右边，然后再将红色盘移动到最右边，三步，完成了。

那如果圆盘数量增加到3，4，5，6，……呢？

这里我们就要学会怎么模拟了，这里有三个圆盘，我们先将上面的两个小的看作一个整体，那么整体过程就可以看作是上面的二阶汉诺塔移动了。

Hanoi_2
所以，抽象地解释，汉诺塔的移动从本质上来说就分为三步：

  • 把上方部分移到中间
  • 把最大盘移到右边
  • 把上方部分移到右边

请注意，如果把柱子从左往右标号为1，2，3的话，那么1、2号柱子的物理意义其实是相同的，怎么理解呢，也就是说，当最上方的n-1个圆盘存在于中介位置时，将其移动到目标柱子3号柱的过程是与它目前处在1还是2无关的，比如说存在于2号柱，也就是左下图的情况，你可以在脑海里将1和2两个柱子互换一下，就变得和上面n=2的物理过程一模一样了。

我们用代码来实现一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Hanoi(vector<int>& A, vector<int>& B, vector<int>& C) {
	int n = A.size();
        move(n,A,B,C);
}
void move(int n,vector<int>& A, vector<int>& B, vector<int>& C){
	if(n==1){
        	C.push_back(A.back());
        	A.pop_back();
        	return;
	}
        move(n-1,A,C,B); //将A上面n-1个通过C移到B
        C.push_back(A.back());//将A最后一个移到C
        A.pop_back();//此时A为空
        move(n-1,B,A,C); //将B上面n-1个通过空的A移到C
}

爬楼梯

楼梯有 $ N $ 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。

爬楼梯问题在实质上是一个斐波那契数列，斐波那契数列的通项公式是这样的：

\begin{equation} F [ n ] = F [ n - 1 ] + F [ n - 2 ] ( n > = 2 , F [ 0 ] = 1 , F [ 1 ] = 1 ) \end{equation}

知道了这个显然就很好编程了，但是我们还是来看一下原理的推导，我研究了许多篇博文，对原理的讲解都不算太侧重，今天我们详细地分解一下。

首先，思想上和上面的汉诺塔问题非常地相似，都是把复杂的问题化成一个个子问题的嵌套。
爬1阶楼梯，显然只有一种方法，即直接爬1阶。（不存在爬两阶超过它的情况）
爬2阶楼梯，则有两种方法，一次1阶，爬2次，和1次2阶，爬1次。
那么爬3阶楼梯呢，我们可以这么看，从最后上楼梯的方案来分类，如果最后一次爬了2阶，那么前面就一共爬了1阶，只有1种方法；如果最后一次爬了1阶，那么前面就一共爬了2阶，有2种方法。1+2,也就是3。

那么更多阶的情况，假设是n阶，都可以用n-1和n-2的情况去反推。

过河卒

实在是来不及写了，只画了个草图，先用这个讲课，回头再补全。
image
题目要求在这里：
棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，A 点 (0,0)、B 点 (n,m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

如果你想亲自去尝试一下这个题目，链接放在这里

这个题目的思路很简单，就是将地图抽象为一个矩阵，在C++里，你可以用二维数组去表示每一个交叉点。我们可以首先将马的控制范围标记为0，也就是说，这里是走不通的，然后从左上角开始往右下角开始标记，走到每个结点的可能方法数，是用走到该结点的左边和上面的结点的方法数之和，从左至右，从上至下依次完善这个矩阵数据，终点坐标的数值也就是所有可行的办法数了。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
using namespace std;
int m, n;
long long map[21][21];
void mark(int x, int y) {
    if (x - 1 >= 0 && y - 2 >= 0)
        map[x - 1][y - 2] = 0;
    if (x - 1 >= 0 && y + 2 <= n)
        map[x - 1][y + 2] = 0;
    if (x - 2 >= 0 && y - 1 >= 0)
        map[x - 2][y - 1] = 0;
    if (x - 2 >= 0 && y + 1 <= n)
        map[x - 2][y + 1] = 0;
    if (x + 1 <= m && y - 2 >= 0)
        map[x + 1][y - 2] = 0;
    if (x + 1 <= m && y + 2 <= n)
        map[x + 1][y + 2] = 0;
    if (x + 2 <= m && y - 1 >= 0)
        map[x + 2][y - 1] = 0;
    if (x + 2 <= m && y + 1 <= n)
        map[x + 2][y + 1] = 0;
}
int main() {
    cin >> m >> n;
    int h_x, h_y;//马的坐标
    cin >> h_x >> h_y;
    for (int i = 0; i < m+1; i++) {
        for (int j = 0; j < n + 1; j++)
            map[i][j] = -1;
    }
    map[0][0] = 1;
    map[h_x][h_y] = 0;
    mark(h_x, h_y);
    for (int i = 0; i < m + 1; i++) {
        if (i > 0) {
            if (map[i][0] == 0);
            else
                map[i][0] = map[i - 1][0];
        }
        for (int j = 1; j < n + 1; j++) {
            if (map[i][j] == 0);
            else if (i == 0) map[i][j] = map[i][j-1];
            else {
                map[i][j] = map[i - 1][j] + map[i][j - 1];
            }
            
        }
    }
    cout << map[m][n];
    return 0;
}