由于迷宫的问题难度太大，有些人没有及时完成，所以这一篇晚发出一天。通过迷宫的问题，暴露出大家对递归掌握的不是很好，今天我们就专门来说说递归。

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天中的迷宫问题。

我是天花板，让我们一起在软件开发中自我迭代。
如有任何问题，欢迎与我联系。

上一篇：天花板编程手把手计划-第1期-第3天