【Linux】C/C++从入门到放弃--深入理解函数（第四节）

• 文章内容如有错误、纰漏希望各位大佬能在评论区指正~

• 啊！一起来学习C/C++吧
• • 第一章 C语言入门
  • • 前言
    • 一、深入理解函数
    • • 1.return语句
      • 2.增量式开发
      • 3.递归
    • 总结
    • • 参考书目

• 学习编程绝不是一件简单的事，尤其是对于零基础的初学者来说。
• 其实C语言是一门很难的编程语言，不懂编译原理、操作系统和计算机体系结构根本不可能学明白。
• 所以本文不会孤立地讲C语言，而是和编译原理、操作系统、计算机体系结构结合起来讲。

之前我们一直在main函数中使用return语句，现在是时候全面深入地理解一下，总的来说return语句有以下的特点：

• 在有返回值的函数中，return语句的作用是提供整个函数的返回值，并结束当前函数的执行。
• 在没有返回值的函数中也可以使用return语句，例如当检查到一个错误时提前结束当前函数的执行。
• 返回布尔值的函数是一类非常有用的函数，在程序中通常充当控制表达式，函数名通常带有is或if等表示判断的词，这类函数也叫做谓词（Predicate）。
• 记住这条基本原理：函数返回一个值相当于定义一个和函数返回值类型相同的临时变量并用return后面的表达式来初始化。例如我们可以这样：

int is_even(int x)
{
	 return !(x % 2);
}
int main(int argc, char *argv[])
{
	int i = 19;
	if (is_even(i)) {
	
	} else {
	
	}
	return 0;
}

根据上面的基本原理我们可以知道：虽然函数的返回值可以看作是一个临时变量，但我们只是读一下它的值，读完值就释放它，而不能往它里面存新的值，换句话说，函数的返回值不是左值。例如下面的赋值语句是非法的：

is_even(20) = 1;

1. C语言的传参规则是按值调用（Call by Value），按值传递，现在我们知道返回值也是按值传递的，即便返回语句写成return x; 返回的也是变量x的值，而非变量x本身，因为变量x马上就要被释放了。

2. 在写带有return语句的函数时要小心检查所有的代码路径（Code Path）。有些代码路径在任何条件下都执行不到，这称为死代码（Dead Code）。例如，如果把&&和||运算符记混了，写出如下代码：

void foo(int x, int y)
{
 	if (x >= 0 || y >= 0) {
	printf("both x and y are positive.n");
	return;
} else if (x < 0 || y < 0) {
	printf("both x and y are negetive.n");
	return;
}
	printf("x has a different sign from y.n");
}

最后一行printf永远都没机会被执行到，是一行死代码(Dead Code)。有死代码(Dead Code)就一定有Bug，你写的每一行代码都是想让程序在某种情况下去执行的，你不可能故意写出一些永远不会被执行的代码，如果程序在任何情况下都不会去执行它，说明跟你预想的情况不一样，要么是你对所有可能的情况分析得不正确，也就是逻辑错误，要么就是像上例这样的笔误，语义错误。还有一些时候，对程序中所有可能的情况分析得不够全面将导致漏掉一些必需的代码路径，例如：

int absolute_value(int x)
{ 
		if (x < 0) {
		return -x;
} else if (x > 0) {
		return x;
}
}

1. 这个函数被定义为返回int，就应该在任何情况下都返回int，但是上面这个程序在x==0时安静地退出函数，什么也不返回，C语言对于这种情况会返回什么结果是未定义的（Undefined）。

2. 通常返回不确定的值，并且在不同的平台和环境下返回值会很不一样。另外，注意这个例子中把-当负号用了而不是当减号用，事实上+号也可以这么用。正/负号是单目运算符，而加减号是双目运算符，正负号的优先级和“布尔代数”讲的逻辑非运算符相同，比加减的优先级要高。

• 目前为止你看到了很多程序例子，也在它们的基础上做了很多改动，在这个过程中巩固所学的知识，但是如果从头开始编写一个程序解决某个问题，应该按什么步骤来写呢？本节提出一种增量式（Incremental）开发的思路，很适合初学者。

例如：我们要编一个程序求平面上的圆的面积，圆的半径以两个端点的座标(x1,y1)和(x2, y2)给出。首先分析和分解问题，把大问题分解成小问题，再对小问题分别求解。这个问题可分为两步：

1. 由两端点座标求半径的长度，我们知道平面上两点间距离的公式是：
   d i s t a n c e = ( ( x 2 − x 1 ) 2 + ( y 2 − y 1 ) 2 ) distance = sqrt{((x2-x1)^{2}+(y2-y1)^{2})} distance=((x2−x1)2+(y2−y1)2) ​
   括号里的部分都可以用我们学过的C语言表达式来表示，求平方根可以math.h中的sqrt函数，因此这个小问题全部都可以用我们学过的知识解决。这个公式可以实现为一个函数，参数是两点的座标，返回值是distance。
2. 上一步算出的距离是圆的半径，已知圆的半径之后求面积的公式是：
   a r e a = π × r a d i u s 2 area = π times radius^{2} area=π×radius2
   也可以用我们学过的C语言表达式来解决，这个公式也可以实现为一个函数，参数是radius，返回值是area。

好了我们现在已经把大问题拆解了，现在可以先写一个简单的函数定义：

double distance(double x1, double y1, double x2, double y2)
{
	 return 0.0;
}

初学者写到这里就已经不太自信了：这个函数定义写得对吗？虽然我是按我理解的语法规则写的，但文中没有和这个一模一样的例子，万一不小心遗漏了什么呢？既然不自信就不要再往下写了，没有一个平稳的心态来写程序很可能会引入Bug。所以在函数定义中插一个return 0.0立刻结束掉它，然后立刻测试这个函数定义得有没有错误：

int main(void)
{ 
		printf("distance is %fn", distance(1.0, 2.0, 4.0, 6.0));
		return 0;
}

编译，运行，一切正常。这时你就会建立起信心了：既然没问题，就不用管它了，继续往下写。

在测试时给这个函数的参数是(1.0, 2.0)和(4.0, 6.0)，两点的x座标距离是3.0，y座标距离
是4.0，因此两点间的距离应该是5.0，你必须事先知道正确答案是5.0，这样你才能测试程序运
算的结果对不对。当然，现在函数还没实现，运算结果肯定是不对的。现在我们再往函数里添
一点代码：

double distance(double x1, double y1, double x2, double y2)
{ 
		double dx = x2 - x1;
		double dy = y2 - y1;
		printf("dx is %fndyis %fn", dx, dy);
		return 0.0;
}

如果你不确定dx和dy这样初始化行不行，那么就此打住，在函数里插一条打印语句把dx和dy的值打出来看看。把它和上面的main函数一起编译运行，由于我们事先知道结果应该是3.0和4.0，因此能够验证程序算得对不对。

一旦验证无误，函数里的这句打印就可以撤掉了，像这种打印语句，以及我们用来测试的main函数，都起到了类似脚手架（Scaffold）的作用：在盖房子时很有用，但它不是房子的一部分，房子盖好之后就可以拆掉了。

房子盖好之后可能还需要维修、加盖、翻新，又要再加上脚手架，这很麻烦，要是当初不用拆就好了，可是不拆不行，不拆多难看啊。写代码却可以有一个更高明的解决办法：把脚手架（Scaffolding）的代码注释掉。

这样如果以后出了新的Bug又需要跟踪调试时，还可以把这句重新加进代码中使用。两点的x座
标和y座标距离都没问题了，下面求它们的平方和：

double distance(double x1, double y1, double x2, double y2)
{ 
		double dx = x2 - x1;
		double dy = y2 - y1;
		double dsquared = dx * dx + dy * dy;
		printf("dsquared is %fn", dsquared);
		return 0.0;
}

然后再编译、运行，看看是不是得25.0。

这样增量式地开发非常适合初学者，每写一行代码都编译运行，确保没问题了再写一下行，这样一方面在写代码时更有自信，另一方面便于调试：总是有一个先前的正确版本做参照，一旦运行出了问题，几乎可以肯定是刚才添的那一行代码出了问题，避免了从很多行代码中去查找分析到底是哪儿出的问题。

在这个过程中printf功不可没，你怀疑哪一行代码有问题，就插一个printf进去看看中间的计算结果，任何错误都可以通过这个办法找出来。以后我们会介绍程序调试工具gdb，它提供了更多的调试功能帮你分析更隐蔽的错误。

但即使有了gdb，printf这个最原始的办法仍然是最简单、最有效率的。最后一步，我们完成这个函数：

#include 
#include 
double distance(double x1, double y1, double x2,double y2)
{ 
		double dx = x2 - x1;
		double dy = y2 - y1;
		double dsquared = dx * dx + dy * dy;
		double result = sqrt(dsquared);
		return result;
}
int main(void)
{ 
		printf("distance is %fn", distance(1.0, 2.0,4.0, 6.0));
		return 0;
}

随着编程经验越来越丰富，你可能每次写若干行代码再一起测试，而不是像现在这样每写一行就测试一次，但不管怎么样，增量式开发的思路是很有用的，它可以节省你大量的调试时间，不管你有多强，都不应该一口气写完整个程序再编译运行，那几乎是一定会有Bug的，到那时候再找Bug就很难找了。

这个程序中引入了很多临时变量：dx、dy、dsquared、result，如果你有信心把整个表达式一次性写好，也可以这样：

double distance(double x1, double y1, double x2, double y2)
{ 
		return sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1));
}

接下来编写area这个函数：

double area(double radius)
{
		 return 3.1416 * radius * radius;
}

给两点的座标求距离，给半径求圆的面积，这两个子问题都解决了，接下来应该把他们组合起来使用：

double radius = distance(1.0, 2.0, 4.0, 6.0);
double result = area(radius);
//也可以这样：
double result = area(distance(1.0, 2.0, 4.0, 6.0));

我们一直把“给半径两端点的座标求圆面积”这个问题当作整个问题来看，如果它也是一个更大的程序当中的子问题呢？我们可以把先前的两个函数组合起来做成一个新的函数以便日后使用：

double area_point(double x1, double y1, double x2, double y2)
{
	 return area(distance(x1, y1, x2, y2));
}

还有一种组合的思路：不是把distance和area两个函数调用组合起来，而是把那两个函数中的语句组合到一起：

double area_point(double x1, double y1, double x2, double y2)
{ 
		double dx = x2 - x1;
		double dy = y2 - y1;
		double radius = sqrt(dx * dx + dy * dy);
		return 3.1416 * radius * radius;
}

• 这样组合是不理想的。如果有些情况只需要求两点间的距离，或者只需要给定半径长度求圆面积，把所有语句都写在一起，太不灵活了，而且会有很多重复代码，一旦在distance函数中发现了Bug，或者要升级distance这个函数采用更高的计算精度，那么不仅要修改distance，还要记着修改area_point。
• 因此，尽可能复用（Reuse）以前写的代码，避免写重复的代码。封装就是为了复用，把解决各种小问题的代码封装成函数，在解决第一个大问题时可以用这些函数，在解决第二个大问题时可以复用这些函数。

解决问题的过程是把大的问题分成小的问题，小的问题再分成更小的问题，这个过程在代码中的体现就是：函数是分层设计的。

distance和area是两个底层函数，解决一些很小的问题，而area_point是一个上层函数，上层函数通过调用底层函数来解决更大的问题，底层和上层函数都可以被更上一层的函数调用，最终所有的函数都直接或间接地被main函数调用。如下图所示：

• 如果定义一个概念需要用到这个概念本身，我们称它的定义是递归的（Recursive）。

数学上确实有很多概念是用它自己来定义的，比如n的阶乘（Factorial）是这样定义的：n的阶乘等于n乘以n-1的阶乘。

如果这样就算定义完了，恐怕跟上面那个词条有异曲同工之妙了：n-1的阶乘又是什么？是n-1乘以n-2的阶乘。

那n-2的阶乘呢？这样下去永远也没完。因此需要定义一个最关键的基础条件（Base Case）：0的阶乘等于1。

0! = 1
n! = n · (n-1)!
因此，3!=32!，2!=21!，1!=10!=11=1，正因为有了基本案例（Base Case），才不会永远没完地数下去，有了1!的结果我们再反过来算回去，2!=21!=21=2，3!=32!=32=6。

下面我们用程序来完成这一计算过程。我们要写一个计算阶乘的函数factorial，先把Base Case这种最简单的情况写进去：

int factorial(int n)
{ 
		if (n == 0)
		return 1;
}

如果参数n不是0应该return什么呢？根据定义，应该return n*factorial(n-1);，为了下面的分析方便我们引入几个临时变量把这个语句拆分一下：

int factorial(int n)
{ 
		if (n == 0)
		return 1;
		else { int recurse = factorial(n-1);
		int result = n * recurse;
		return result;
}
}

factorial这个函数居然可以自己调用自己？是的。自己直接或间接调用自己的函数称为递归函
数。这里的factorial是直接调用自己，有些时候函数A调用函数B，函数B又调用函数A，也就
是函数A间接调用自己，这也是递归函数。

我们以factorial(3)为例分析整个调用过程，如下图所示：

局部变量的变化情况:

1. main()有一个局部变量result，用一个框表示。
2. 调用factorial(3)时要分配参数和局部变量的存储空间，于是在main()的下面又多了一个
   框表示factorial(3)的参数和局部变量，其中n已初始化为3。
3. factorial(3)又调用factorial(2)，又要分配factorial(2)的参数和局部变量，于是在main()和factorial(3)下面又多了一个框。
4. 局部变量与全局变量 讲过，每次调用函数时分配参数和局部变量的存储空间，退出函数时释放它们的存储空间。
5. factorial(3)和factorial(2)是两次不同的调用，factorial(3)的参数n和factorial(2)的参数n各自有各自的空间，虽然它们的变量名相同都是n，虽然我们写代码时只写了一次参数n，但运行时却是两个不同的参数n。
6. 由于调用factorial(2)时factorial(3)还没退出，所以两个函数的参数n同时存在，所以在原来的基础上多画一个框。
7. 依此类推，请读者对照着图自己分析整个调用过程。读者会发现这个过程和前面我们用数
   学公式计算3!的过程是一样的，都是先一步步展开然后再一步步收回去。

随着函数调用的层层深入，存储空间的一端逐渐增长，然后随着函数的层层退出，存储空间的这一端又逐渐缩短，这是一种具有特定性质的数据结构。

它的特性就是：只能在某一端增长或缩短，并且每次访问参数和局部变量时只能访问这一末端的单元，而不能访问内部的单元，比如当factorial(2)的存储空间位于末端时，只能访问它的参数和局部变量，而不能访问factorial(3)和main()的参数和局部变量。

具有这种性质的数据结构称为堆栈或栈（Stack）。每个函数调用的参数和局部变量的存储空间（图里的一个小方框）称为一个栈帧（Stack Frame）。

系统为每个程序的运行预留了栈空间，函数调用时就在这个栈空间里分配栈帧，函数返回时就释放栈帧。

在写一个递归函数时，你如何证明它是正确的？

可以用数学归纳法（Mathematical Induction），用数学归纳法来证明只需要证明两点：基础方案（Base Case）正确，递推关系正确。

写递归函数时一定要记得写基础方案（Base Case），否则即使递推关系正确，整个函数也不正确。

到目前为止我们只学习了全部C语言语法的一个小的子集，但是现在应该告诉你：这个子集是完
备的，它本身就可以作为一门编程语言了，以后还要学很多的C语言特性，但全部都可以用已经
学的这些特性来代替。

也就是说，以后要学的C语言特性使得写程序更加方便，但不是必不可少的，现在学的这些已经完全覆盖了 “程序和编程语言”讲的五种基本指令了。有的读者会说循环还没讲到呢，是的，循环后面才讲，但有一个重要的结论就是递归和循环是等价的，用循环能做的事用递归都能做，反之亦然，事实上有的编程语言（如某些LISP）只有递归而没有循环。

[1] 宋劲杉.Linux C编程一站式学习
[2] 鸟哥.鸟哥的 Linux 私房菜：基础学习篇 第四版
[3] K&R.The C Programming Language.
[4] Niklaus Wirth. Algorithms + Data Structures = Programs.