写给电子专业同学的C语言教程
C/C++语言教程
递归
一般来讲，递归对于初学者来说是一个比较困难的内容，就我个人的学习经历来说，递归也是我在初学时比较头痛的一部分。对于这种情况，我想总结一下我学习中遇到的困难，然后在与大家分享递归思想的过程中，尽可能扫清那些影响我的障碍，让递归的学习梯度更缓一些，从而帮助大家更快地学习递归。
首先我想来说一下在我初学递归的过程中，我遇到了哪些困难：首先最重要的一条，我最早接触递归是通过一道习题接触的，就是大名鼎鼎的汉诺塔问题，算是个经典的递归问题了。但是经典归经典，我却不认为初学递归应该从汉诺塔开始，因为汉诺塔本身并不属于掷色子或者猜拳那种人尽皆知的游戏，想要去理解汉诺塔，首先要先看其规则并烂熟于心，然后就是汉诺塔使用了两个递归去完成，自然比单个递归要困难一些：以循环为例，通常的学法是先学明白单循环，再接触双层循环，接受起来才更容易些。因此，在接下来的讲解中，我将从一个非常非常简单的例子：打印1-5这五个数字为例，讲解递归操作的使用。
在讲解例子之前，我们先整体描述一下递归，递归即函数自己调用自己。
对于上述的定义，我们拆开来阐述一下：“函数自己调用自己”，这句话可以缩句为“函数调用”，调用谁先不管，要做的事情是函数调用，这件事要首先明确。在之前的课程中我们已经学习了函数的调用，尤其是我们将一段完整的，具有通用性的且需要多次使用的语句封装成一个函数，并在主函数中进行调用，这种操作我们已经非常熟悉，下面我们来看一个简单的例子：
1 |
|
运行结果
1 | 12345 |
在这个例子中我们可以看到函数的多个函数依次调用：main()
调用 E()，E() 调用
D()，D() 调用
C()，C() 调用
B()，B() 调用 A()，当函数
A() 运行结束后，函数自动退出，然后就会返回
B()，返回到 B() 后 B()
也走到其函数体的最后了，因此 B() 也退出，然后就会返回
C()，就这样依次返回，最终回到 main()，执行
return 0; 。
在循环中，我们将具有相似结构的语句进行简化，如：
1 | /*本段代码为伪代码。*/ |
那么同样的，对于有着相同形式的函数，就像最前面一段代码中那样，函数
A() 到函数 E()
的函数体具有高度的相似性，我们是否也可以通过类似于循环那样的方法来实现同样的功能呢？
答案是可以的，我们可以只使用函数 A() ，代码如下：
1 |
|
运行结果：
1 | 12345 |
接下来我们画图来分析一下，这段代码是如何工作的。
现在你应该对于递归的自调用有一定的概念了，那么现在我们来讨论一个问题，那就是，为什么是递归？毕竟我们以及有循环了，在刚才的示例中，我们递归能做的事情，循环可以做的更好，并且还好理解，我们何苦呢。
为了解决目前我们的递归看起来还没啥用的情况，我们引入第二个问题：十进制正整数转二进制数。
首先，解决这个问题，我们首先要知道十进制正整数转二进制数的算法。这个算法是非常简单的，这里我取我们数字电路课本中的例题来说明一下算法：
算法如下：
- 十进制正整数不断除以二，记录余数
- 当除法运算结果为0时，保留这次运算的余数并停止运算
- 将余数从下往上取出，在等号右侧从左往右依次列出
这个算法，使用循环的话，我们会遇到一些麻烦的事情，让循环变得不那么好用了，因为，我们第一个得到的结果，需要在最后被打印出来。
这时候就到了递归登场的时候了，因为递归是函数的自调用，当函数一层一层的调用后，还需要一层一层的退出，比较的话，可以这样看待循环和递归，循环只是前进，而递归要去一趟回一趟，也就是两趟。
这种特性使得我们能够轻松使用递归实现先得到的结果最后展示，在最终公布“十进制正整数转二进制数”题目的答案前，我们插一个小实例，来看一下，递归如何实现先得到的结果最后展示的：
1 |
|
运行结果：
1 | 54321 |
这段代码看着根前面的那段代码很想，唯一不同的是5、6两行的顺序颠倒了，这样导致的结果就是，程序将会先走到调用的最底层，然后在返回的时候在逐次打印，具体如下图展示。
最后我们来看一下十进制正整数转二进制数的实现：
1 |
|
运行结果
1 | 53 |
目前，我们已经使用递归来解决实际问题了，也算是从不懂到会用了。耶！
但是，光看别人写是不够的，因为很多书写的细节对出初学者来说是难以注意到的。值得在你们自己开始写递归前就重点强调一下的书写细节是递归的停止条件。
在循环中，尤其是最常用的 for
循环，具有很明确的开始和截至的标识，在递归中，我们没有一个循环变量小i来直到我们设置递归的层数，但是，无穷的递归是不被允许的，无穷递归很快就会使程序运行内存中一片叫栈的区域爆满（或者专业点，叫溢出）。在上面所有的递归程序中，我们都可以看到，自调用的函数，我们在开头都设置了条件判断，只有在一定条件内的输入才能往后进行迭代，否则就
接下来，我将带领大家，在前面已经理解递归的基础上，从理解汉诺塔的规则开始，一点一点写出整个汉诺塔代码，一行一行的说明我在书写汉诺塔程序时是如何进行思考的。
首先是汉诺塔问题描述，摘录自维基百科：
有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：
- 每次只能移动一个圆盘；
- 大盘不能叠在小盘上面。
提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。
问：如何移？最少要移动多少次？
然后是摘自维基百科的代码
1 |
|
运行结果：
1 | 3 |
根据运行结果，我们可以画出3个圆盘的汉诺塔是如何实现移动的：
然后问题就来了，因为我们会发现一个问题，那就是，根本找不到规律啊，递归要求一个函数，也就是说一种方法，只改变一下输入参数，不断调用这一个方法就能实现整个过程，但是看上面的图根本就无法找到规律啊。
那么，我们该如何解决现在面临的问题呢？是不是可以考虑，可能是取的数量太少，我们可以试试圆盘数量为4个或者5个？
1 | 4 |
好家伙，我们会发现一个要命的问题——太多了，到五个的时候，就已经接近30次移动了。这要是画出来，可有点麻烦，那怎么办呢？
答案很简单，查资料！因为这实在是一个很普遍的问题，还是来看看其他人是如何理解这个问题的吧。
我们打开知乎直接搜汉诺塔+递归，很快，就出来了一个好回答，我们引用来给大家看一下：
举例来说，如果要把一个N层汉诺塔从A搬到C，那么：
如果前N-1层可以找别人搞定，咱只管搬第N层，会不会变得非常容易？
你看，这一下就简单了：这时当它只有两层就好了，先把前N-1层看作一个整体，把它搬到B；然后把最下面的第N层搬到C；然后再把前N-1层从B搬到C。
把上面的话变成图像，就是这样子的，我们以四圆盘汉诺塔为例子说明：
好的，看到这个图不知道大家会不会有些疑问哈，可能会有同学觉得，这样搬会不会违反汉诺塔的游戏规则了？emmm，如果你最后的结果是这样搬动的确实是不行的，但是关键在于，我们按照搬动顺序去寻找递归方法是行不通的，我们需要寻找一种能解决问题的通用方法（这里的通用是指对每一层圆盘移动的通用方法），然后我们在解决完问题后，再去调整顺序输出，来实现满足游戏规则的搬动方法。
因此，上述操作，确实可以帮助我们将4个圆盘，从A移动到C，并且我们可以注意到，从第3行到第4行，因为移动的圆盘都比C上的大圆盘小，故移动是随意的，即ABC三个底座都可以放圆盘。
观察上图，我们可以看到，第一列中有四个圆盘，从第一步到第二部和从第三步到第四步在规则的制约下都不是可以一步实现的，但是因为每一次变化都依旧有三个底座可用，故具有移动方法上的相似性，这使得函数的自调用成为可能。
我们可以看到，随着列数往后数，我们处理的问题的规模在逐渐下降，最初是4个圆盘，第二列时，我们关注的就成了3个圆盘，这样依次下推，最终我们会得到一种情况，这种情况下只有一个圆盘，如图：
我们观察放大部分中的最后一列，可以看到，最后一列中所有的操作都是将圆盘从A移动到C，这种特性说明了每一次递归的终点都是“将圆盘从A移动到C”，如果你回到上面看代码，你会发现代码中真正打印的移动操作都是从a到c
1 |
|
函数指针
回调函数
维基百科：
在计算机程序设计中，回调函数，或简称回调（Callback 即call then back 被主函数调用运算后会返回主函数），是指通过参数将函数传递到其它代码的，某一块可执行代码的引用。这一设计允许了底层代码调用在高层定义的子程序。
百度百科：
回调函数就是一个被作为参数传递的函数。在C语言中，回调函数只能使用函数指针实现，在C++、Python、ECMAScript等更现代的编程语言中还可以使用仿函数或匿名函数。
回调函数的使用可以大大提升编程的效率，这使得它在现代编程中被非常多地使用。同时，有一些需求必须要使用回调函数来实现。
最著名的回调函数调用有C/C++标准库stdlib.h/cstdlib中的快速排序函数qsort和二分查找函数bsearch中都会要求的一个与strcmp类似的参数，用于设置数据的比较方法。
回调函数的理解：
回调函数是一个函数
回调函数将会成为另一个函数的参数
在C语言中回调函数需要使用函数指针来实现
回调函数重要意义在于：底层的代码可以调用上层定义的子程序
回调函数的形象化理解：
- 如一酒店提供叫醒服务（对应位底层实现的库函数），那么
- 如果不使用回调函数的思想：你提供时间（参数），则叫醒服务将会在所设置的时间叫醒你（将参数传入函数）
- 如果使用回调函数的思想：你提供时间（普通参数）和叫醒的方法（函数指针），则叫醒服务将会在所设置的时间按照你提供的方法叫醒你
- 如一酒店提供叫醒服务（对应位底层实现的库函数），那么
回调函数实例：
如你编写了一个排序函数如下（冒泡排序，代码参考此处）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void sort(int cmd[], int len)
{
int i, j, temp;
for (i = 0; i < len - 1; i++)
{
for (j = 0; j < len - 1 - i; j++)
{
if ((cmd[j] > cmd[j + 1]))
{
temp = cmd[j];
cmd[j] = cmd[j + 1];
cmd[j + 1] = temp;
}
}
}
}此段代码中核心的判断逻辑是：
如果
(cmd[j] > cmd[j + 1])，则交换(cmd[j] > cmd[j + 1])，这种方式实现效果为，较小的数字排在前面，交大的数字排在后面——正序输出，即输出结果：2 25 56 88 100这段代码存在的问题是，如果不去看
sort()函数的实现，就不能去修改正序输出还是逆序输出。首先我们很明显能看到，我们有控制输出为正序or逆序的需求，但是不同于自己写的Demo，我们在实际工程中，可能会出现某些情况使得我们难以修改
sort()函数内部的代码：比如有些库函数的实现不是开源的，你无法查看源码或修改源码；或者有些库函数的实现代码非常复杂，你不希望全部浏览而是希望能在外部直接调用。在这些情况下，我们需要使用回调函数来帮助我们去控制库函数代码的一部分实现细节，而我们自己在书写一些供其他人使用的代码时，也可以使用回调函数来让用户自己补充一些功能细节将上述代码改写为回调函数的版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void sort(int cmd[], int len, int (*p)(int, int))
{
int i, j, temp;
for (i = 0; i < len - 1; i++)
{
for (j = 0; j < len - 1 - i; j++)
{
if (p(cmd[j], cmd[j + 1]))
{
temp = cmd[j];
cmd[j] = cmd[j + 1];
cmd[j + 1] = temp;
}
}
}
}这里修改的方案为：
- 在函数参数列表中加一个函数指针提供外部接口供用户实现
if()判断中调用函数指针(*p)(cmd[j], cmd[j + 1])
使用回调函数，实现了解耦合：
没有回调函数的情况下，每一个函数其功能的实现是完全确定的，如果我们想修改其中的任意一部分功能，我们都必须重写此函数。也就是说，我们想要自己调整的功能与函数实现（通常指库函数）是紧密耦合在一起的。如果我们希望从外部可以选择函数实现中的一部分细节，或者在实现函数时希望未来一部分实现方式由用户来完善，那么我们就应该使用回调函数将那部分功能与（库）函数进行解耦合。
验证代码：
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
52
53
54
55
56
57
58
int small_to_big(int x, int y)
{
return (x > y) ? 1 : 0;
}
int big_to_small(int x, int y)
{
return (x < y) ? 1 : 0;
}
void sort(int cmd[], int len, int (*p)(int, int))
{
int i, j, temp;
for (i = 0; i < len - 1; i++) {
for (j = 0; j < len - 1 - i; j++) {
if ((*p)(cmd[j], cmd[j + 1])) {
temp = cmd[j];
cmd[j] = cmd[j + 1];
cmd[j + 1] = temp;
}
}
}
}
void sort(int cmd[], int len)
{
int i, j, temp;
for (i = 0; i < len - 1; i++)
{
for (j = 0; j < len - 1 - i; j++)
{
if ((cmd[j] > cmd[j + 1]))
{
temp = cmd[j];
cmd[j] = cmd[j + 1];
cmd[j + 1] = temp;
}
}
}
}
int main()
{
int i;
int size;
int cmd[] = { 88, 56, 100, 2, 25 };
size = sizeof(cmd) / sizeof(cmd[0]);
sort(cmd, size, small_to_big);
sort(cmd, size, big_to_small);
//sort(cmd, size);
for (i = 0; i < size; i++)
{
printf("%d ", cmd[i]);
}
printf("\n");
return 0;
}
分割线内为引用
回调函数实例（很有用）
一个GPRS模块联网的小项目，使用过的同学大概知道2G、4G、NB等模块要想实现无线联网功能都需要经历模块上电初始化、注册网络、查询网络信息质量、连接服务器等步骤，这里的的例子就是，利用一个状态机函数（根据不同状态依次调用不同实现方法的函数），通过回调函数的方式依次调用不同的函数，实现模块联网功能，如下：
1 | /********* 工作状态处理 *********/ |
复制
所以，如果有人想做个NB模块联网项目，可以copy上面的框架，只需要修改回调函数内部的具体实现，或者增加、减少回调函数，就可以很简洁快速的实现模块联网。