天花板编程手把手计划-第1期-第4天
由于迷宫的问题难度太大，有些人没有及时完成，所以这一篇晚发出一天。通过迷宫的问题，暴露出大家对递归掌握的不是很好，今天我们就专门来说说递归。
1. 递归
递归其实是通过一个函数不断调用自身来实现一组简单重复的功能。递归有一道非常经典的题目是打印斐波那契数列。我们先看看这道题。
1.1 斐波那契数列
一个数列中，每个数字都是前两个数字之和，这样的数列就是斐波那契数列。数列的前两个数字为1。
斐波那契数列有一个基础的解法，大概大家都能想到，代码如下：
#define PRINT_CNT 10
void main()
{
int i;
int arr[PRINT_CNT];
for (i = 0; i < PRINT_CNT; i++)
{
if (i == 0 || i == 1)
{
arr[i] = 1;
}
else
{
arr[i] = arr[i - 1] + arr[i - 2];
}
printf("%d ", arr[i]);
}
}
这段代码通过简单循环的方式打印出了数列的前10个数字，如果需要打印更多只需要修改PRINT_CNT这个宏。算法很朴素，这里就不多说了。
1.2 寻找递归子结构
在我们考虑一个问题是否能够通过递归的方法来解决时，首先要分析问题是否有一个反复迭代的子结构。这道题中，从第三个数字起，每个数字都是前面两个数字求和，这个动作是完全相同的简单重复。
于是我们设计代码框架如下：
#define PRINT_CNT 10
int Fib(int n)
{
}
void main()
{
int i;
for (i = 1; i <= PRINT_CNT; i++)
{
printf("%d ", Fib(i));
}
}
我们需要通过函数Fib()来计算出第n个位置的元素。之后我们就通过循环打印出每一位数就OK了。递归子结构就需要通过函数Fib()的不断递归调用来完成。
1.3 设计递归函数
在设计函数Fib()时，我们需要考虑两个问题：
- 递归跳出条件
由于递归是不断地调用自身，如果没有跳出条件的话就会陷入到无限死循环中。这一点需要最先考虑。
这道题中，由于前两个数是固定的，因此当n为1和2时不需要递归，直接返回1就行。这就是跳出条件。
- 递归条件
需要考虑每一次递归和前一次的关系。
这道题中，每次递归都要通过自身调用得到前两次递归的结果，之后求和返回。这就是递归条件。
我们来看看源码：
int Fib(int n)
{
if (n == 1 || n == 2)
{
return 1;
}
else
{
return Fib(n - 1) + Fib(n - 2);
}
}
是不是很简单。运行一下，看看结果如何。
这道题目用递归解的效率并不高，但作为递归的例题却很容易理解，所以很多教科书把它当做递归的例题。
1.4 递归调用过程
整个程序的调用过程如图所示，仔细看看其实是一个二叉树。递归的一个重要特点就是可以表示成一个N叉树，N大于等于1。
2. 抛硬币问题
接下来我们看看抛硬币的问题：把一个硬币抛5次，打印出所有可能出现的情况。1表示正面，0表示背面。
我们把这道题用递归的思想去分析，你会发现：
- 抛硬币的次数是固定的，可以作为跳出条件。当抛到第五次时，不再继续递归调用。
- 每次抛硬币都是一次递归的过程，虽然抛硬币每次都是相互独立的，但对我们最终打印的结果是有影响的。
我们把抛硬币的全部可能性表示成下面这个图:
图中只表示了前四次抛硬币的可能性，一个标准的二叉树。从根结点到每一个叶子结点的路径都是我们最终要输出的一行结果。
注意：没有学过二叉树的同学不用紧张，这里只是用了这个名词，并没有涉及到相关的数据结构知识。看懂图就行。
3. 程序实现
今天我们先给出完整的程序：
#include
#define MAX_THROW_TIME 5
int g_arr[MAX_THROW_TIME];
void Throw(int face, int cnt)
{
int i;
g_arr[cnt] = face;
cnt++;
if (cnt >= MAX_THROW_TIME) // 跳出递归
{
for (i = 0; i < MAX_THROW_TIME; i++)
{
printf("%d ", g_arr[i]);
}
printf("\n");
}
else // 继续递归
{
Throw(0, cnt);
Throw(1, cnt);
}
}
void main()
{
Throw(0, 0);
Throw(1, 0);
}
全局变量g_arr数组用来保存每一次抛硬币的结果。
重点来看Throw()函数，这个函数的功能是在数组g_arr中标记出抛第cnt次的一种结果。注意，它只是标记一种结果，也就是二叉树中第cnt层的一个节点,至于是哪一个节点就要看是被哪一个节点调用的了。
Throw()函数有两个参数：
- face
表示硬币的两个面，值为1表示正面，值为0表示反面。
- cnt
用来记录抛硬币的次数。通过这个变量我们设置了退出条件，当达到我们设置的次数MAX_THROW_TIME时，打印g_arr中的全部内容。这就是一种完整的可能。
来看看执行结果吧：
4. 作业完成情况
大部分同学都用了二进制的方式打印出了全部结果，功能上完全正确。个别人也用了递归的思想，不过他使用了随机数的方式，模拟了真正的抛硬币过程。
随机的方式不是我们这道题所要求的，我们只是要打印出所有的可能性，因此每一次递归都是固定的，一个正面一个反面。我们要做的只是通过不同的递归路径来修改每一次抛硬币的结果，从而得到全部的可能。
5. 课后作业
5.1 作业一
编程实现把1~9九个数字填入九宫格中，满足每行、每列和对角线上的三个数字和为15。如图所示。
注意：由于结果不唯一，只要打印出一种满足条件的结果即可。
5.2 作业二
想想如何使用递归的方法解决天花板编程手把手计划-第1期-第3天中的迷宫问题。
我是天花板，让我们一起在软件开发中自我迭代。
如有任何问题，欢迎与我联系。
