由于迷宫的问题难度太大，有些人没有及时完成，所以这一篇晚发出一天。通过迷宫的问题，暴露出大家对递归掌握的不是很好，今天我们就专门来说说递归。
1. 递归
递归其实是通过一个函数不断调用自身来实现一组简单重复的功能。递归有一道非常经典的题目是打印斐波那契数列。我们先看看这道题。
1.1 斐波那契数列
一个数列中，每个数字都是前两个数字之和，这样的数列就是斐波那契数列。数列的前两个数字为1。
斐波那契数列有一个基础的解法，大概大家都能想到，代码如下：
#define PRINT_CNT 10void 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 10int 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 递归调用过程
图中只表示了前四次抛硬币的可能性，一个标准的二叉树。从根结点到每一个叶子结点的路径都是我们最终要输出的一行结果。
注意：没有学过二叉树的同学不用紧张，这里只是用了这个名词，并没有涉及到相关的数据结构知识。看懂图就行。
3. 程序实现
今天我们先给出完整的程序：
#include #define MAX_THROW_TIME 5int 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。如图所示。
注意：由于结果不唯一，只要打印出一种满足条件的结果即可。
作者：天花板
链接：https://www.jianshu.com/p/cc312e23ed69